Interrogating Paradigms in Self-supervised Graph Representation Learning
Authors: Puja Trivedi
Mark Heimann
Danai Koutra
Jayaraman J. Thiagarajan
Venue: ICLR 2022 Submitted (2022)
Keywords: Graph Neural Networks
Contrastive Learning
Self-supervised Learning

Abstract: Graph contrastive learning (GCL) is a newly popular paradigm for self-supervised graph representation learning and offers an alternative to reconstruction-based methods.However, it is not well understood what conditions a task must satisfy such that a given paradigm is better suited. In this paper, we investigate the role of dataset properties and augmentation strategies on the success of GCL and reconstruction-based approaches. Using the recent population augmentation graph-based analysis of self-supervised learning, we show theoretically that the success of GCL with popular augmentations is bounded by the graph edit distance between different classes. Next, we introduce a synthetic data generation process that systematically controls the amount of style vs. content in each sample- i.e. information that is irrelevant vs. relevant to the downstream task- to elucidate how graph representation learning methods perform under different dataset conditions. We empirically show that reconstruction approaches perform better when the style vs. content ratio is low and GCL with popular augmentations benefits from moderate style. Our results provide a general, systematic framework for analyzing different graph representation learning methods and demonstrate when a given approach is expected to perform well.

Under review as a conference paper at ICLR 2022
INTERROGATING PARADIGMS IN SELF-SUPERVISED GRAPH REPRESENTATION LEARNING
Anonymous authors
Paper under double-blind review
ABSTRACT
Graph contrastive learning (GCL) is newly popular paradigm for self- self-super graph representation learning and offers an alternative reconstruction baseed methods. However, it is not well understood what conditions task must sat- isfy such that a given paradigm is better suited. In this paper, we investigate the role of dataset properties and augmentation strategies on the success of GCL and reconstruction-base graph-based based analysis of self-supervised learning, we show theoretically that the success of GCL with popular augmentations bounded by the graph edit distance between different classes. Next, we introduce synthetic data generation process that systematically controls the amount of style vs. content in each sample- i.e. information that is irrelevant vs. relevant the downstream task- elucidate how graph representation learning methods perform under different dataset con- ditions. We empirically show that reconstruction approaches perform better when the style vs. content ratio is low and GCL with popular augmentations benefits from moderate style. Our results provide a general, systematic framework for an- alyzing different graph representation learning methods and demonstrate when a given approach expected to perform well.
approaches. Using the recent population augmentation
INTRODUCTION
Analyzing graph-structured data is essential for many real-world applications and graph neural net- works (GNNs) have emerged as a popular solution for challenging prediction tasks. However, these tasks often have limited labeled data due to prohibitive procuration costs and require models to possess strong generalization abilities to be practically useful. For example, in molecular property prediction, obtaining training labels requires expensive lab experiments and, at test time, models must predict properties for novel candidate molecules (Hwang et al. 2020, Duvenaud et al.) 2015 Zimik et al. 2018). Unsupervised graph representation learning is a natural paradigm in such cases, where graph contrastive learning (GCL) is promising approach over using pre-training tasks (Hu ct al. 2020).
While recent findings (Arora al. 2019 HaoChen al. 2021 Tian al. 2020 K Kügelgen ett al. 2021 Zimmermann et al., [021] Wang & Isola [020 Purushwalkam & Gupta 2020) have investigated what makes for successful visual contrastive learning, similar understanding remains lacking for GCL. Furthermore, in computer vision, reconstruction-baseed approaches using an au- toencoder framework (Kingma & Welling 2014), updated with modern encoder architectures and data augmentation, are emerging as an alternative paradigm that avoids negative sampling or large batch sizes (Falcon et al., 202T). Reconstruucion--aan based approaches (Kipf Welling, 2016) have not yet been similarly revisited with improved GNN architecture designs or augmentations for self- supervised graph representation learning. Moreover, due to complications arising from the discrete, non-Euclidean nature of graph datasets, analysis from visual contrastive learning (VCL) cannot be straightforwardly extended to a graph setting. Therefore, remains unclear under what circum- stances reconstruction CL-based approach is expected to perform well on given task.
In this paper, we investigate, theoretically and empirically, the conditions that enable a given unsu- pervised learning approach to perform well. Specifically, we first show theoretically that the success of GCL with generic graph augmentations (GGA) introduced by GraphCL (You et al.) 2020a) is dependent the graph edit distance between classes. Next, address the elephant in the room:

---

Under review as a conference paper at ICLR 2022
that untrained GNNs have enough inductive bias to nullify the benefits of unsupervised pre-training on benchmark graph classification datasets. Therefore, we introduce a carefully designed synthetic dataset and conduct an extensive evaluation to better understand the behavior of both reconstruc- tion and CL approaches. Here, we demonstrate that the effectiveness of different unsupervised approaches over strong untrained baselines can be understood through style content decompo- sition: the proportion of relevant information for a task (content) and irrelevant information (style) that each example in dataset contains.
Our contributions are as follows: (i) We provide theoretical analysis of when contrastive learning expected to work well, showing that this depends on the graph edit distance of samples within and across classes; (ii) We systematically evaluate reconstruction as an alternative unsupervised paradigm to contrastive learning for graphs, including introducing augmentation-an aaggeete graph autoencoders (A (AAGAE). Further, we empirically show to what extent untrained GNN models are competitive baseline in terms of accuracy, invariance, and sample complexity; and (iii)mWe identify style vs. content trade-off in graphs and introduce extensive benchmark setup that can carefully control this trade-off. Using our benchmark, we show how not only the ratio of style vs. content but also how generie versus content-awar augmentation impacts different learning paradigms.
2 BACKGROUND: UNSUPERVISED REPRESENTATION LEARNING FOR GNNs
While the general approach of pre-training can be either supervised (Hu et al. ) or unsu- pervised, we focus on the latter. In this section, we formalize unsupervised representation learning (URL) for graphs and discuss two widely adopted approaches, namely graph contrastive learning and reconstruction-basee -aaee learning. Appendix [A. contains additional related work on self-supervised learning and data augmentation for graphs
Graph Contrastive Learning. Contrastive learning (CL) frameworks learn representations by max- imizing similarity between positive or augmented examples, and at the same time minimizing simi- larity between negative or uncorrelated examples. Formally, let X = (z...... Fy, denote a dataset consisting of un-augmented (clean) samples, where each v, (G,, F,) corresponds to a tuple con- taining the adjacency matrix G3 E [o, 1j and node feature matrix F.. Let A represent a set of augmentations over X: namely the generic graph augmentations (GGA) introduced by You et al,, 2020a): (i) node dropping,
(ii) edge perturbation, (iii) attribute masking and (iv) sub-grapl sampling. Furthermore, let X be the set of all augmented samples given X, and {x; = A(T:). , Ij = A(T.)) be considered a positive pair.
GraphCL. parallels SimCLR (Chen et al. 2020a) and uses the normalized temperature scaled cross entropy (NT-XENT) loss learn representations by contrasting the representations of positive pairs and negative samples. Specifically, let f be a graph feature learner, such that f(z;) e.g., a GNN with a global READOUT layer. i.e., READOUT Rxd RRd. Given batch size B, similarity function, sim: (Rd, Rd) - [0, 1), temperature parameter, T, and positive pair, {a,, z5); the NT-XENT loss defined as:
E Rd
exp (sim (ZT
l log 2B
[|=4]] exp (sim (z:, 2x) /T)
k=1
Here, the numerator encourages the representations for 24, Ij to have high similarity, while the denominator encourages representations of negative pairs (k & i) to have low similarity. By maxi- mizing similarity between positive samples, we expect the representations become invariant the properties modified by augmentations. Correspondingly, models learn to perform instance discrimi- nation where each sample defines its own class and the augmented samples also belong to this class. Other recent GCL frameworks follow this general formulation but differ in the choice of the objec- tive function and the augmentation strategy. For example, InfoGraph (Sun et al., 2020 maximizes the mutual information between sampled subgraphs (local) and pooled graph (global) representa- tions. MVGRL (Hassani & Ahmadi, 2020) contrasts representations of graphs augmented through diffusion processes at node and graph scales. While this work focuses GraphCL, other formula-
tions including InfoGraph, DGI (Hjelm et al., 2019), and GMI (Peng et al. 2020 can be derived as instances of this general framework.
Reconstruction-Be Based Approaches. In computer vision, auto-encoding frameworks enriched with sophisticated model architectures and strong data augmentations (Falcon al. 2021) are currently
2

---

Under review as a conference paper at ICLR 2022
being revisited alternative unsupervised learning paradigm that is less dependent on large batch-sizes (Chen et al.; 2020a) and negative sampling strategies (Kalantidis et al. 2020) when compared to CL. Given that graph datasets are often significantly smaller than vision datasets and negative sampling strategies may be difficult to design, such approaches are particularly relevant to self-supervised graph representation learning and bear revisiting in light of stronger GNN architec- tures and augmentations.
Formally, let g: (Gi, + Rnxd be an encoder that outputs node representations, h Raxd [0, 1j be a decoder that predicts the edges of G; given node representations, and READOUT Raxd + Rd provide graph representations given node representations. Then, vanilla graph auto- encoder minimizes: [ - Gill.. where h is often defined as a (g(z))((z;) (z;))) and the aggre- gated graph representation 2; = READOUT (G F.)) is used to perform downstream tasks. Given that graphs are generally sparse, standard implementations sample an equivalent number of positive and negative edges to ensure stable training. Variational graph auto-encoders (Kipf & Welling 2016) reparameterize node representations and add a KL divergence term the reconstruction loss simi- lar to (Kingma & Welling, 2014). As we will argue in this paper, reconstruction -aaseetttoo---ddddddd approaches enhanced with suitable augmentations can be an effective alternative for GCL, under specific condi- tions. We choose to focus on reconstruction tasks as it is more general than task-specific pretraining tasks and more amenable to theoretical analysis (Khemakhem et al., (020). In subsequent sections, seek to understand when and why given method performs well. We begin by taking a closer look at the performance of graph URL using benchmark datasets.
3 A CLOSER LOOK INTO GRAPH URL USING BENCHMARK DATASETS
Designing an unsupervised representation learning pipeline for graph graph-structured data requires se- lecting from a number of components, including encoder architecture, data augmentation, strategies for leveraging inductive bias, and training paradigms. different components on downstream performance, so practitioners can appropriately select them for their needs and determine if URL or pre-training will improve representation quality. To this end, we begin by performing an empirical study on benchmark datasets that considers different: (i) lev- els of inductive biases by incorporating data augmentation and varying the amount of training; (ii) representation learning paradigms (CL, coonsstuctioonbaseeee (iii) GNN architectures (GIN, GCN, GAT etc.). We note that we are the first to implement and benchmark the augmentation augmented graph auto-encoders (AAGAE) as stable econstructionn-base approach for graph URL.
important to understand the impact of
While our empirical analysis offers several insights into different components of graph URL pipelines, we are unable to evaluate context-aware augmentations (CAA) as they are difficult to realize on standard graph benchmarks. CAA have been critical to the advancements in visual CL and the remainder of this paper investigates if CAA have similar promise for graph URL. In Section 4, we extend analytical tools from visual CL to characterize the behaviour of generic graph aug- mentations (GGA). In Section 5 we introduce a novel, synthetic benchmark that gives us control over the style vs. content ratio in the synthesized samples. This enables systematic evaluation of the potential gains to be obtained from CAA. We begin by evaluating the quality of representations obtained not only through GCL and reconstruction--ict based approaches but also from surprisingly ef- fective, untrained GNN encoders.
3.1 REPRESENTATION LEARNING STRATEGIES
We consider three flavors of unsupervised representation learning: (i) Graph contrastive learning: For a representative GCL approach, we select GraphCL with GGA as a popular and effective method for graph classification. Following You et al. (2020a), we use random node-dropping or sub- graph sampling at 20% of the graph size as the augmentation strategy; (ii) Reconstruction-bbssll In addition to standard graph autoencoders (GAEs), we extend AAVAE (Falcon et al.) (021) to the graph domain and introduce angmentation-augmeennn minimizes the reconstruction loss with respect to the original sample, AAGAE minimizes the recon- struction loss between the original and the reconstruction for an augmented sample to learn repre- sentations that consistent with respect to augmentations: ||G; ( II) We use the same augmentations and encoder architecture as GraphCL for fair comparison and include a straight- through estimator in the decoder for better training (Jang et al. 2017); and finally (iii) Untrained
graph autoencoders (AAGAE). While GAE
3

---

Under review as a conference paper at ICLR 2022
representations: We include untrained GNNs as important baseline and find that representations from randomly initialized models often perform comparably to unsupervised approaches.
There is some folk wisdom that untrained GNNs can be surprssiggy competitive with trained mod- els. Early GNN works noted that even an untrained model may have strong inductive bias suitable for node-level tasks (Kipf & Welling 2017). For graph-level transfer learning, Xu et al. (2021) consider an untrained GIN model as a baseline, finding it obtains competitive although generally inferior results. A recent blog post performs limited exploratory analysis of graph classification using untrained embeddings obtained from simple GCN model (Safronov) 202T). Our analysis here (extended consider different architectures Appendix A.34 far more comprehensive, showing precisely in what ways untrained models may be competitive.
Table I: Inductive Bias Benchmark Datasets. We report the performance of untrained N-layer GIN
encoders against 3-layer encoders trained through GraphCL (You et al.) (2000a) or reconstruction approaches (GAE/AAGAE). Results for GraphCL are taken from the paper and we Tollow the same evaluation protocol. Best results are indicated in bold; results within standard deviation are underlined.
Dataset
Untrained (3)
(ntrained(4)
Untrained
GraphCI.
GAF
AAGAR
MUTAG (188)
85.76 7.38
86.36 + 6.51
86.73 + 10.33
86.80 + 1.34
87.76
3.00
88.23 + 0.98
PROTEINS (1113)
73.64 + 5.464
74.46 + 4.09
74.22 2.85
74.39 + 0.45
75.36 + 0.4
74.77 + 0.43
NCI1 (4060)
70.65 +: 1.99
70.36 + 3.11
70.49 + 2.42
77.81 + 0.41
79.48 + 0.44
79.75 1: 1.25
DD (1187)
73.23 +: 8.25
72.15 7.25
77.08
4.18
78.62 + 0.40
+
77.59
0.64
RDT- (2000)
72.34
64.57
8.03
67.32
7.41
0.84
79.75 + 1.25
79.95
4.39
IMDB-B B (1000)
67.22 + 7.77
61.26 + 7.01
60.43 + 5.92
71.14
71.70 + 0.36
71.26 + 0.305
0.875
0.850
Untrained
0.825
GAE
AAGAE
0.80
0 Sup. Training A GAE
GraphC1
0.75
PROTEINS
0.70
PROTEINS
NC11
0.65
IMDB BINARY
REDDIT-BINARY
0.5
0.6
0.7
0.8 0.9
0.10 0.25
0.50
0.75
1.00
Sim. (Estimated Invarlance)
Semi. Sup. Label Ratio
(a)
(b)
Figure Invariance vs. Acc on TUDatasets. While trained models do see an improvement in both accuracy and invariance, we see that this improvement often minimal over an untrained model, suggesting that GGA augmentations introduce invariance that is not always useful to the downstream tasks; (b) Sample Complexity on TU Datasets. We perform semi-supervised learning TU Datasets with various amounts of labeled data. For REDDIT-BINARY, pretraining does improve sample complexity. GAE/AAGAE have slightly better complexity than the supervised baseline on IMDB-BINARY On PROTEINS, pretraining also does not have clear benefits.
3.2 EVALUATION METRICS
While prediction accuracy the downstream task is important criterion for choosing a represen- tation learner, we consider two other metrics to empirically illustrate the benefits of these methods, or lack thereof, over the untrained representations. Specifically, we quantify how training with unsu- pervised methods affects the invariance of representations with respect to augmentations, and sample complexity. These metrics are selected because they are well-aligned with the objectives of potential applications. For example, in molecular property prediction, it is desirable to have models that are invariant to small measurement discrepancies and can quickly generalize new distributions. We define these measures and describe how they are computed as follows.
Invariance: When training with NT-XENT, as GraphCI. does, the representation similarity between augmented pairs is maximized and models learn invariances to augmentations. AAGAE also en- forces consistency to natural and augmented samples. However, it is unclear if (i) models are actually learning invariant representations and (ii) if this property is valuable to downstream task performance. To measure this property, for a given sample F,, we generate 300 randomly aug- mented samples {x] ... 2200 compute the average cosine similarity between x;, Note, using cosine similarity as proxy for the invariance property is well-motivated by NX-ENT.
4

---

Under review as a conference paper at ICLR 2022
Sample Complexity: If unsupervised learning is used as the pre-training step, then it is expected that the pre-trane trained model will have improved sample complexity. We consider if this holds true for GraphCL, GAE and AAGAE. Specifically, after unsupervised training. we include linear classifier layer to the backbone or encoder. Then, we train the model, end-to-end, in a supervised fashion, where we vary the size of the labeled dataset, extending the setup of (You et al., 2020a).
GGA introduces invariance that has limited improvements in performance. Fig. La plots the invariance of GraphCL, GAE, AAGAE, and untrained models on benchmark TU datasets. As noted in Tab. D untrained models often perform comparably to trained ones (5 5% difference). However, we see that training with GCL or reconstruction leads improved invariance. This suggests that the learning invariance was not necessary for downstream task performance. While designing better augmentations is a difficult but obvious solution (Zhao et al. 2020 Kong et al.) 2020), in Sec. [5]
we find that even optimal augmentations are often unable to surpass supervised performance and
discuss implications of this result.
Pretraining has limited benefits on sample complexity. Given that GCL or reconstruction did not lead to considerable improvements in accuracy over a untrained baseline or introduce meaningful invariance, we investigate if pretraining leads to better sample complexity. As shown in Fig. Tb we find there is no clear benefit to pretraining. On REDDIT-BINARE better accuracy across all label ratios. For IMDB -INBAB,,.R..... reconstruction based approaches offers a slight improvement. The results are mixed for PROTEINS. We note that the supervised model did not consistent improvements as the labeled ratio increased and suspect this is related to the random data-splits (Dwivedi et al.) 2020).
the fully supervised model has
Our empirical analysis demonstrates the unreasonable effectiveness of untrained GNNs and high- lights the uneven benefits GGA with respect to invariance, sample complexity and accuracy. More- over, in the appendix, we show that URL leads minimal improvements for expressive architec- tures, such as PNA (Corso et al. 22200). In the next section, we use the recently proposed Population Augmentation Graph (HaoChen et al. 202T) to better understand the limitations of GGA, as they are routinely used when it is unclear how to leverage domain knowledge as graph augmentations.
USING POPULATION AUGMENTATION GRAPHS TO ANALYZE GGA
Recent attempts to analyze theoretically the performance of contrastive learning often assumes that sample views are independent, a condition clearly violated by data augmentation (Arora et al.) 2019 Tosh al. 202T). To avoid this assumption, HHoCChn et al, (202T) recently introduced the notion of population augmentation graph, which represents augmented samples as nodes and edges as the likelihood of generating a given pair of augmented samples from the same clean sample. HaoChen et al. (202I) also provably showed that well-designed augmentations will lead to tight subgraphs (partitions) in the population graph that correspond with downstream class labels. They show that true class labels can be recovered, up to some error, by performing spectral decomposition on this graph and propose a matrix factorization based objective function to perform the decomposition.
In this section, we leverage population augmentation graphs (PAGs) for analyzing contrastive learn- ing with graph data, and show that employing generic graph augmentations from (You et al. (2220)) will lead subgraphs in the PAG that are dependent on the graph edit distance (GED) between sam- ples of different classes: that is, the minimum number of graph edit operators (operations such as node dropping edge perturbation that also form the basis for the augmentations commonly used in contrastive learning) needed to transform one sample into another. This implies that performing spectral decomposition on this graph will not align with true class labels if the average GED of sam- ples between two different classes is smaller than the average GED of samples between the same class. Equivalently, generic graph augmentation (GGA) can be interpreted as imposing GED as the implicit metric for representation similarity, and the success of GCL with GGA is dependent on how appropriate GED is for a given task.
More specifically, our analysis is comprised of the following steps: (i) defining the population aug- mentation graph; (ii) showing that GGA can be decomposed in graph edit operators; (iii) describing graph characteristics of the PAG; and finally (iv) showing that the resulting subgraphs of the PAG are determined by GED, which may not necessarily align with downstream class labels. We follow the notation in (HaoChen et al. 202T).
5

---

Under review as a conference paper at ICLR 2022
4.1 CONSTRUCTING THE PAG WITH GENERIC GRAPH AUGMENTATIONS
Given a natural dataset X. let A(- be the distribution of augmentations given a natural sample T, or, intuitively, the probability of generating a particular augmented sample from the large but finite set of all possible augmented versions of T. Then, X' == U2exxA(-1T)) Note, the tuple (x: = A(r), = A())) is considered a positive pair.
Population Augmentation Graph HaoChen et al. 20221: Let G be the population graph, where all N samples in augmented set X' form the nodes and W E IR NNN is the corresponding adjacency matrix. The edge weight between two nodes and x' is defined
Wa. == (((
Intuitively, Wn.rr is larger, relatively easier generate the augmented pair from the same natural sample.
We first observe that augmentations defined by GraphCL, (such as node dropping, edge perturbation, and sub-graph sampling) can be directly decomposed using standard graph edit operators (node dropping, node addition, edge dropping, and edge addition). For example, an edge perturbation augmentation be represented Further, note that GraphCL assumes that constraining augmentations to a fraction, ", of the overall graph size will preserve task-relevant information, and only one augmentation may be applied to a graph at a time. Then, for a single sample, 34 = (G;, Fi), the maximum edit distance of an augmented sample x' A(T) is:
set of edge drops and edge additions between {x, A(x)) }
max 71
where & Vi are the edge/node sets. Now, since graphs are discrete, the augmentation severity is restricted and only one edit can be applied at time, we completely delineate the set of allowable augmentations given E, A,, and can determine the size of this set.
For example, consider the node dropping augmentation and let my E z be the number of allowable node drops for G,. Then, there
TV
ND.
(D ク
allowable augmented samples. Further, note that augmentations are applied randomly, so any sample in the augmentation set is equally likely, up to node permutation. This means, we can exactly define A(r|z), as | A similar analysis can be used for other augmentations. For ease of exposition, we focus on one augmentation here.
Then, we observe
A(x #0 <> E A
(2)
GED(x, 7s.
Intuitively, x must exist in the augmentation set of to have non-zero probability and the augmen- tation set is defined by all graphs within "/ edits. This implies Wz,z' will be large when x, x' jointly appear in the augmentation set of many different natural samples. As such, we have defined all pos- sible nodes in G as well how the edges are defined and can discuss implications of the structure of the population graph induced by GGA.
4.2 ANALYZING POPULATION AUGMENTATION GRAPH STRUCTURE
HaoChen et al. (202T) show that performing spectral decomposition on the augmentation graph provably recovers underlying classes if the partitions or subgraphs in the augmentation graph can be aligned to downstream classes. We now show how these partitions are related to GED and how the structure of these partitions relates to task performance. Clearly, for strong downstream performance, partitions must contain more samples from the same class than of different classes.
Recall Eq. and Eq. define when given edge will exist between samples. Now, clearly, determin- ing how many edges will cross between ground-tran truth classes can be determined by measuring the edit distance between samples of different classes. Formally, consider simple binary task. where : {(GED(z; 1T) < t/ + r y # y(2z)} corresponds to a set of edges across classes and क == (GGD (., S n 7j v( ) = y(rr)}} is the set of edges within classes. Then,

---

Under review as a conference paper at ICLR 2022
Style Ratio: 0.5
Style Ratio: 1.0
Style Ratio: 2.0
Style Ratio: 3.0
Figure 2: Synthetic Dataset Generation. We create six class, graph classification dataset by first, selecting of six unique motif's and then injecting 1-3x copies into randomly generated tree. Here, the motifs completely determine the class, and are considered "content" (shown in red). To vary the amount of style, the size of the background tree graph (shown in blue) is ratio of the number of "content" nodes. Above are examples of varying style ratios. Our datasct goes beyond binary, benchmark datasets and allows for content- aware augmentations, critical component to understanding the maximal performance GCL frameworks.
if | > | it is not possible to learn well-aligned partitions because partitions will contain mix of classes. Therefore, if spectral contrastive learning is performed using GGA, there is some fixed enror, e, that is directly determined by the average GED between classes, as shown.
While our analysis leverages PAG and the spectral contrastive loss, HaoChen et al. (202T) show that their proposed loss function can be extended to other popular contrastive loss functions and also empirically performs well. Therefore, our results suggest generally that the success of graph contrastive learning with GGA is dependent on the GED between classes. The augmentation set of a given sample is determined by its graph size, and thus it should be more difficult to achieve invariance GGA augmentations for larger graphs. Third, the above analysis may offer path to deriving bounds on the generalization to certain distribution shifts, for example graph size shifts.
5 A STYLE VS. CONTENT PERSPECTIVE FOR EVALUATING CONTENT-AWARE AUGMENTATIONS
While the above analysis identifies untrained networks strong baseline for URL and char- acterizes GGA's behavior, it remains unclear how to improve different components of GCL and reconstruction-bait based approaches such that the additional expense of pretraining is justified. Given that existing augmentations are far from optimal (see Sec. one avenue of improvement is through better augmentation design. However, graph data augmentation known to difficult (Kong al.) 2020 Zhao et al. 2020) and it is unclear if the different paradigms will benefit equally from im- proved augmentations. To that end, we first take the perspective that graph samples can be decom- posed into style (irrelevant information) vs. content (task relevant information). We then introduce a synthetic data generation process that controls the amount of style vs. content in dataset sam- ples (see Fig. (2), and allows for oracle, content-aware augmentations (CAA). Using this dataset, we validate the effectiveness of augmentations and introduce a valuable benchmark to the community.
Recent theoretical works in VCL. also build upon a similar style vs. content perspective. For ex- ample, von Kügglgen et al. (202I) introduced a latent variable model to show that self-supervised training with data augmentations is able to recover style vs. content partition in the latent repre- sentation and Zimmermann et al. (202T) showed that is possible to invert the data generating process using contrastive learning and augmentations. Our work differs in that our data generation process operates directly in the observed domain, instead of latent variables as in (von Kügelgen et al. 2021). and we leverage oracle augmentations to better understand the performance of different frameworks. Synthetic Data Generation: The proposed data generation process consists of three components:
set of C' motifs. M, that uniquely determine C' classes, a random graph generator, RBG(nn) parameterized by the number of nodes (we can also equivalently define this based on number of edges), and p. the style multiplier, which controls how much irrelevant information is included in a sample. To generate sample, we attach randomly generated background graph (ie., style com- ponent) to a motif (i.e., content) in accordance to the style multiplier. While this process is simple, it addresses several limitations often encountered in GCL evaluation. Specifically, this process (i) allows for varying levels of content-aware augmentation (i.e., edges that can be perturbed directly in the background graph without harming the motif); (ii) is easily extended beyond binary classifica- tion; (iii) contains relatively large number of samples and (iv) offers a natural test bed for GNN size generalization or transfer learning.
7

---

Under review as a conference paper at ICLR 2022
Graph Contrastive Learning
Reconstruucion--aese Approaches
1.0
0.8
0.7
0.5
2.5
3.0
0.5
2.5
3.0
Style Multiplier
Style Multiplier
83
Sup. Training
Untrained
A
GAE
V
AAGAE Rand.,
GraphCL
ContentPres.
ContentPres,,
Rand.,
Figure 3: Effeet of Style vs. Content Ratio on Different Paradigms:
We evaluate the performance of con-
trastive and reconstruction approaches with content preserving and random augmentations the ratio of style vs. content changes. As expected, reconstruction methods perform best low style regimes. While we see that content aware augmentations improve performance, especially for GCL, in high style regimes, it remains difficult to match the supervised performance.
Experimental-Setup: We let = 6 and define RBG(n) through a random tree generator, where n is 5% of the nodes belonging the motif. To make the task more challenging, randomly insert be- tween 1-3 motif copies into each sample. We explore two different augmentation strategies, namely random edge dropping and content preserving edge dropping, where only edges in the background graph are dropped. We parameterize these augmentations by the number of edges in the total entire and background graphs, respectively. We do not consider any additional node features, though that extension would be straightforward. We use a 5-layer GIN-based encoder for both our GraphCL backbone and GAE/AAGAE encoders and the models are evaluated using a linear probing protocol (Chen et al. 2020a). See appendix A.2 for more details.
5.1 BALANCING STYLE vs. CONTENT
Many real graph datasets can be understood through the aforementioned partitioning of relevant vs. irrelevant information. For example, molecules can be split into functional groups (content) and carbon rings (style). A natural question is whether reconstruction based approach or contrastive learning approach is preferable if there is some intuition on the ratio of style vs. content (i.e., many carbon rings vs. few). We make the following observations from Fig.
Reconstruction-basee approaches perform well in low style regimes. Note that as the amount of style increases, the problem inherently becomes harder. However, regimes where there is little style content (irrelevant information), reconstruction-based approaches should perform well particular as model will only learn to recover the relevant information. Conversely, GCL with GGA risks corrupting content, and generating false positives Thus, we expect the accuracy of reconstruction based approaches to fall more sharply as the amount of style increases, which indeed do see in Fig. We also find that that CAA helps GCL perform considerably better than with GGA, and that less severe generic augmentations are better; this supports the hypothesis that GCL succeeds when, whether by augmentation design or simply the composition of the data, there is less risk of the augmentations corrupting content.
of distribution samples.
Content-aware augmentations are not silver bullet. Optimal augmentations generate views that only share task-relevant information and minimize other task-irrelevant information (Tian et al.) 2020). For the proposed dataset, this would correspond removing the entire background graph. We restrict augmentations to removing 60% of the style portions and find even with strong content- preserving augmentations, unsupervised approaches significantly under meder-perform when compared to fully supervised models. This is in stark contrast to VCL where strong data augmentation is crit- ical component to surpassing performance of supervised models on variety of vision tasks (Chen) et al. 2020a). Our analysis suggests that other framework components, such as more expressive chitectures (Chen et al. 2020b) Xu et al., 2019 Velickovic et al., 2018 Corso et al. 2020; Hamilton et al. 2017) and sampling strategies (Kalantidis et al.) 2020; Grill et al. 2020 Chen & He (020), must also be developed before GCL sees the same success. Furthermore, we note that the gain from CAA in high-style regimes much less pronounced for reconstruction approaches than for
8

---

Under review as a conference paper at ICLR 2022
1.0
X Sup. Training Untrained
0.9
83 Sup. Training
0.9
À GAE AAGAE GraphCL No Aug.
0.8
AAGAE Graphcl
Acc
0.8
ContentPres.. 20%
ContentPres. 20%
ContentPres., Rand., 20%
0.5
ContentPres, 60%
0.7
Rand.,
0.4
Rand., 60%
0.75
Cosine Sim. (Estimated invariance)
Sup. Label Ratio
Figure 4: (a) Invariance (a)
(b)
Accuracy Syuthetic Datasets. We measure the invariance random aug- mentations, when p 0.5; (b) Sample Complexity on Synthetic Dataset. We perform cemi-supervised learning when & = 1.0 with various amounts of labeled data. GraphCL has considerably better performance than recomstruction-baseee methods. Content-aware augmentations are useful for both paradigms.
GCL. This may partially be attributed to increased difficulty in reconstructing larger graphs. More sophisticated decoders and algorithms may help improve performance.
5.2 EVALUATION
Invariance to random edge dropping at 20% of the graph after performing unsupervised training when p 0.5 is shown in Fig. Almost all methods improve the untrained baselines in accuracy and invariance. We find that all reconstruction-batt low style regime. In contrast, GCL models that are more invariant tend be more accurate, which may suggest that for this learning paradigm, learning to be invariant to augmentations can improve accuracy. Interestingly, supervised training is the most accurate but the least invariant-this reminds us the pursuit of expressive GNN models that most successfully map distinct graphs to distinct representations Xu et al. (2019) is helpful in supervised settings, though without the guidance of task supervision, unsupervised learning may benefit from greater representation invariance.
Invariance:
methods have high invariance in this
Sample Complexit: We measure the performance of different methods when p = and at dif- ferent labeling ratios in semi-supervised setting. While CAA improves the sample efficiency of reconstruction- bbasd methods with respect to GGA, we see that (i) GAE outperforms AAGAE across all labeling rates, and (ii) all considered accostruction-basee methods are not able match the performance of GCL or supervised performance. This suggests that AAGAE may converge to a more unstable loss landscape, but also highlights our observation the end of Sec. 5.l..5.1hhh augmen- tations are limited in what they can accomplish, and may require technical advances such as more sophisticated decoders come into their own the extent they have in computer vision.
CONCLUSION
In this paper, we seek to understand the behavior of GCL and reconstruction-base. approaches when performing unsupervised graph representation learning. We show theoretically that the success of GCL with popular, generic graph augmentations is directly dependent on the average graph edit dis- tance between classes. Our empirical study shows detail the competitiveness of untrained GNNs on benchmark datasets to help the community understand what benefits to expect from training. We demonstrate for both GCL and reconstruction-bat baaeed methods, which we consider in greater detail for unsupervised graph representation learning including with a new method A AAGAE, that generic graph augmentation does not introduce meaningful invariance or reliably improve model sample complexity on these benchmarks. Thus, introduce synthetic benchmark with a controlled style vs. content decomposition to understand how much can gained from optimal content-aware augmentations and better compare the GCL and reconstruction paradigms. Our work provides ful frameworks and evaluation tools to better understand the performance unsupervised graph representation learning, contributions expect be of great interest this burgeoning field.

---

Under review as a conference paper at ICLR 2022
7 REPRODUCIBILITY STATEMENT
For reproducibility, we provide details about data generation appendix A.2 For baselines, we build off the code provided by the authors and follow the authors' guidelines the hyperparam- eters. We will also release code at this link:
REFERENCES
Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, and Nikunj Saunshi. A theoretical analysis of contrastive unsupervised representation learning. CoRR, 2019.
Karsten M. Borgwardt, Cheng Soon Ong. Stefan Schönauer, S. V. N. Vishwanathan, Alexander J.
Smola, and Hans-Peter Kriegel. Protein function prediction via graph kernels. In Proceedings Thirteenth International Conference Intelligent Systems for Molecular Biology, 2005.
Ting Chen, Simon Komblith, Mohammad Norouzi, and Geoffrey E. Hinton. A simple framework for contrastive learning of visual representations. In ICMI,, 2020a.
Ting Chen, Simon Kornblith, Kevin Swersky, Mohammad Norouzi, and Geoffrey E. Hinton. Big self-supervised models are strong semi-supervised learners. In NeurIPS 2020, 2020b.
Xinlci Chen and Kaiming He. Exploring simple siamese representation learning. CoRR, abs/201 1.1566,,, 2020.
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Velickovic. Principal neighbourhood aggregation for graph nets. In NeurIPS, 2020.
David Duvenaud, Dougal Maclaurin, Jorge Aguilera-Iparraauin Rafael Gómez-Bombarelli, Tim- othy Hirzel, Alán Aspuru-Guut Guzik, and Ryan Adams. Convolutional networks on graphs for learning molecular fingerprints. In NeurlPS, 2015.
Vijay Prakash Dwivedi, Chaitanya K. Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. CoRR, 2020.
William Falcon, Ananya Harsh Jha, Teddy Koker, and Kyunghyun Cho. AAVAE: augmentation- augmented variational autoencoders. CORR, 2021.
Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre H. Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Ávila Pires, Zhaohan Guo, Mohammad Gheshlaghi Azar, Bilal Piot, Koray Kavukcuoglu, Rémi Munos, and Michal Valko. Bootstrap your latent A new approach to self-supervised learning. In NeurlPS, 2020.
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NeurIPS, 2017.
Jeff Z. HaoChen, Colin Wei, Adrien Gaidon, and Tengyu Ma. Provable guarantees for self- supervised deep learning with spectral contrastive loss. CORR, 2021.
Kaveh Hassani and Amir Hosein Khas Ahmadi. Contrastive multi- view representation learning on graphs. In ICMI, 2020.
R. Devon Hjelm, Alex Fedorov, Samuel Trischler, and Yoshua Bengio. Learning deep representations by mutual information estimation and maximization. In ICLR, 2019.
Karan Grewal, Philip Bachman, Adam
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay S. Pande, and Jure Leskovec. Strategies for pre- pre-training graph neural networks. In ICLR, 2020.
Doycong Hwang, Soojung Yang, Yongchan Kwon, Kyung-Hoon Lee, Grace Lee, Hanseok Jo, Seyeol Yoon, and Seongok Ryu. Comprehensive study molecular supervised learning with graph neural networks. J. Chem. Inf. Model,, 2020.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-softman In ICLR, 2017.
10

---

Under review as a conference paper at ICLR 2022
Y. Kalantidis, M. Bülent Sariyildiz, N. Pion, P. Weinzaepfel, and D. Larlus. Hard negative mixing for contrastive learning. In NeurIPS, 2020.
Zekarias T. Kefato and Sarunas Girdzijauskas. Self-supervised graph neural networks without ex-
plicit negative sampling. CoRR, 2021.
lyye Khemakhem, Diederik P. Kingma, Ricardo Pio Monti, and Aapo Hyvärinen. Variational toencoders and nonlinear ICA: A unifying framework. In AISTATS, 2020.
Diederik P. Kingma and Max Welling. Auto-encoding variational bayes. In ICLR, 2014.
Thomas N. Kipf and Max Welling. Variational graph auto-encoders. CoRR, 2016.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net-
works. In ICLR, 2017.
Kezhi Kong, Guohao Li, Mucong Ding, Zuxuan Wu, Chen Zhu, Bernard Ghanem, Gavin Taylor, and Tom Goldstein. FLAG: adversarial data augmentation for graph neural networks. CoRR, 2020.
Nils M. Kriege and Petra Mutzel. Subgraph matching kernels for attributed graphs. In JCML, 2012.
Yixin Liu, Shirui Pan, Ming Jin, Chuan Zhou, Feng Xia, and Philip S. Yu. Graph self-supervised learning: A survey. CoRR, abs/2103.00011, 2021. URL https://aaiivorrg/////1....00000
Zhen Peng. Wenbing Huang. Minnan Luo, Qinghua Zheng, Yu Rong, Tingyang Xu, and Junzhou Huang. Graph representation learning via graphical mutual information maximization. In Pro- ceedings of The Web Conference 2020, pp. 259-2701 2020.
Senthil Purushwalkam and Abhinav Gupta. Demystifying contrastive self-supervised learning: In- variances, augmentations and dataset biases, 2020.
Jiezhong Qiu, Qibin Chen, Yuxiao Dong, Jing Zhang, Hongxia Yang, Ming Ding, Kuansan Wang, and Jie Tang, GCC: graph contrastive coding for graph neural network pre-training. In SIGKDD. ACM, 2020.
Vadcem Safronov. Almost free inductive embeddings out perforrrorm trained graph neural networks in graph classification in range of benchmarks. https:/towardssaaassinnee wow.aacccccm/mmoottt...oo induc five-embeddings-oout pettoor--trrriieeedde nerep---nurlllneeworsss in- claph-classification 1ace36
8bcl 2021. Accessed: 2021-10-05.
Ali Shafahi, Mahyar Najibi, Amin Ghiasi, Zheng Xu, John P. Dickerson, Christoph Studer, Larry S. Davis, Gavin Taylor, and Tom Goldstein. Adversarial training for free! In NeurlPS, 2019.
Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M.
Borgwardt. Weisfeiler-Ichman graph kernels. J. Mach. Learn. Res., 2011.
Fan-Yun Sun, Jordan Hoffmann, Vikas Verma, and Jian Tang. Infograph: Unsupervised and semi- supervised graph-level representation learning via mutual information maximization. In ICLR, 2020.
Shantanu Thakoor, Corentin Tallec, Mohammad Gheshlaghi Azar, Rémi Munos, Petar Velickovic, and Michal Valko. Bootstrapped representation learning graphs. CoRR, abs/2102.06514, 2021. URL https//ariv.orraas2200.....
Yonglong Tian, Chen Sun, Ben Poole, Dilip Krishnan, Cordelia Schmid, and Phillip Isola. What makes for good views for contrastive learning? In NewrIPS, 2020.
Christopher Tosh, Akshay Krishnamurthy, and Daniel Hsu. Contrastive learning, multi-view dundancy, and linear models. In Algorithmic Learning Theory, 16-19 March 2021, Virtual Con- ference, Worldwide, volume 132 of Proceedings of Machine Learning Research, pp. 1179-1206. PMLR, 2021. URL http:///c/d// wwt.smmlrss......... 322tosh21a..nt
Aäron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predic- tive coding. CoRR, 2018
11

---

Under review as a conference paper at ICLR 2022
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liö, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
Petar Velickovic, William Fedus, William L. Hamilton, Pietro Liò, Yoshua Bengio, and R. Devon Hjelm. Deep graph infomax. In ICLR, 2019.
Julius von Kügelgen, Yash Sharma, Luigi Gresele, Wieland Brendel, Bernhard Schölkopf, Michel Besserve, and Francesco Locatello. Self-supervised learning with data augmentations provably isolates content from style. CoRR, fass2106.046199 2021.
Nikil Wale and George Karypis. Comparison of descriptor spaces for chemical compound retrieval and classification. In (ICDM, 2006. doi: 10.1109//CDM.2006.339
Tongzhou Wang and Phillip Isola. Understanding contrastive representation learning through align- ment and uniformity on the hypersphere. In ICML, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? ICLR, 2019.
Minghao Xu, Hang Wang, Bingbing Ni, Hongyu Guo, and Jian Tang. Self-supervised graph-level representation learning with local and global structure. In ICML, 2021.
Pinar Yanardag and S. V. N. Vishwanathan. Deep graph kernels. In SIGKIDD, 2015. doi: 10.1145/
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. NeurlPS, 2020a.
Yuning You, Tianlong Chen, Zhangyang Wang, and Yang Shen. When does self-supervision help graph convolutional networks? CoRR, abs/2006.09136, 2020b. URL https://aaxiivorr///s/0000.... 9136
Jiahui Yu, Zhe Lin, Jimei Yang, Xiaohui Shen, Xin Lu, and Thomas S. Huang. Generative image inpainting with contextual attention. CoRR, abs/1 fobs/180.000 80100999, 2018. URL http://arxxiv.or/abb//ii 01.07892
Tong Zhao, Yozen Liu, Leonardo Neves, Oliver J. Woodford, Meng Jiang, and Neil Shah. augmentation for graph neural networks. CoRR, 2020.
Data
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Graph contrastive learning with adaptive augmentation. WWW, 2020.
Roland S. Zimmermann, Yash Sharma, Steffen Schneider, Matthia Bethge, and Wieland Brendel. Contrastive learning inverts the data generating process. In ICML, 2021.
Marinka Zitik, Rok Sosič, and Jure Leskovec. Prioritizing network communities. Nature Commu- nications, 2018
12

---

Under review as a conference paper at ICLR 2022
A
APPENDIX
A.1 UNDERSTANDING GENERIC GRAPH AUGMENTATIONS
We expand our discussion on the connections between generic graph augmentations and graph edit distance. We also discuss how the graph edit distance between dataset samples influences the struc- ture of the population augmentation graph HaoChen et al. (2021). a recently introduced tool to understand contrastive learning.
Table Notation
Symbol
Definition
X
the original or natural dataset.
X
set of all augmented data. data sample containing graph and node feature tuple, (G4, F.) Edge set of G,, Node of G,-
24
&
7 E 1)
augmentation strength. Controls the % of edges or nodes that may be perturbed by the selected augmentation Augmentation, A, applicd to the natural sample distribution of augmentations given natural sample, Tq. of allowable augmentations given
A(T)
A()az.)
B(z)
E 2 [x
positive, symmetric distance matrix where D., = GED(2,
TE 2
column vector containing max. number of allowable perturbations per sample. column vector providing the labels of all natural samples.
y 00 1
A.1.1 GGA AND GRAPH EDIT DISTANCE
Graph edit distance (GED) is used capture similarity between two graphs. Intuitively, it captures the cost of making elementary edit operations on a graph, 91. to transform it to be isomorphic to another graph, g2- Given two graphs, 91: 92.
GED (91.92)
min (et JEP
cee))
.98) 1
where P (g1, 92) is the set of paths (series of edit operations) that transforms into 92, is i-th edit operation the path, and c(c,) is the cost of the particular edit. In this work, we consider node insertion, node deletion, edge deletion and edge addition the elementary graph edit operators as these are well-aligned to the augmentations defined in You et al. (2020a), namely node dropping. edge perturbation, attribute masking, and sub-graph, sampling. While GED is typically defined on graph structure, our analysis can be extended to include categorical node attributes by introducing graph operator that performs "replacement" whenever graph's node attributes disagree. Then, the GED is the cost of structural changes and the number of disagreements hetween their attributes. Categorical variables are common in molecular classification tasks, where attributes correspond to elements, and discrete node attributes are often used when analyzing GNNs (Xu et al. 2019). We of I per operation, such that GED counts the number operations required to transform one graph into another.
also consider constant
For example, let (g. ga) represent the original and augmented graph respectively, where we perform node dropping to obtain 9a- Recall that the node dropping augmentation may only drop up to some fraction of nodes g. Then, clearly the minimum cost path can then found using only node deletion operators, and the DED(g
(g. 9a) is bounded by the number of allowed node drops. Similarly, ga was obtained through the edge perturbation augmentation, which randomly adds or removes fraction of edges, then GED(g, 9a. is bounded by the number of allowable edge modifications and can be obtained using only edge addition//eletion operators. (Here, we allow nodes without edges to still exist, so performing node addition//elltion would not result in lesser GED.) The sub-graph sampling augmentation extracts a connected sub-gres sub-graph that contains at most fraction of total nodes. The minimum path can then be defined using only node deletions, e.g. where the
13

---

Under review as a conference paper at ICLR 2022
operator is applied to all nodes not in the sampled sub-graph. Therefore, GED(g. 9a) is bounded by [gl - lal.
Given the aforementioned discussion, GED and make the following remarks. Please see Table 2 for a complete list of notation.
now define the set of allowable augmentations using
Definition 1 (Set of Allowable Augmentations). Let A be generic graph augmentation (node
dropping, etc). Then, all allowable augmented samples induced by A(za) have graph edit distance less than max Vil. 7|E,]) } to Vt. Equivalently:
(xx)) {x': :GED(E' xx)) & max
Remark A.1 (Upper-bound on Size of Augmentation Set). The size of (zxx.) can be upper-bounded through a combinatorial or counting process. For example, to determine ( when the considered augmentation node dropping, we can delineate all sets of possible nodes with size upto >/Val- Formally, the upper-bound on the number of samples generated using node dropping are:
DAJ!
B T
( Jトカ!
We note that this value is an upper-bound because isomorphic pairs are treated as two separale graphs. Furthermore, note the size of the augmentation set grows exponentially with graph size.
Definition (Overlapping Sample). An augmented sample, x', is considered an overlapping sample belong the augmentation set of multiple natural samples: x! E BB(,,)Az E B((z)) where + j.
Using Def. 2 we show that overlapping examples must exist given certain conditions on graph edit distance of samples in X.
Remark A.2 (Existence of Overlapping Samples). Consider two samples I; and Ty. Let ri
max ( MM A& and = max(>) (. IfGED (τ(,;)) < rt+Ty, then 3x' B(z,)Aa'
( Le. at least one augmented sample belongs to both the induced augmentation sets.
Definition 3 (Invalid Augmented Samples). We consider an augmented sample, x. to be an invalid sample, i B(x;)) Ax B(x,)) (an overlapping sampling), and y: # Yı-
Claim A.1. Given D, D.T.y, we can lower-bound the number of overlapping samples in the empirical data distribution as _xJE((....xx] 1(D - T; - -, S 0) where 1 the indicator function. Furthermore, if we consider oracle label information, we can lower bound the number of invalid samples as Ee.je(1.....xI] 11 ((D;; r, r,)ly; y₁ 0).
Proof. r; + F is the total number of edit operations that can be applied to either samples x, or Zy- If the graph edit distance between samples i and is smaller than this, then it is possible to reach the same augmented sample somewhere on the edit path that turns T; into 2; regardless of which endpoint we start from. This augmented sample constitutes an overlapping sample, or an invalid sample if the class labels of v, and x, differ. Note that there may multiple such augmented samples that can be created from either I; zy; indicator function counts per pair of samples, and thus helps constitute a lower bound.
A.1.2 DISCUSSION ON INVALID SAMPLES
An invalid sample does not have clear label because we do not know which natural label should be assigned to it. This can incur instability in discriminative methods if the invalid sample's loss minimized with different labels over the course of training. enforcing consistency because such methods will use the invalid sample enforce consistency with respect to two different classes. We note that invalid samples will occur for any method that uses GGA and most methods will incur some irreducible error from training
is also problematic for methods
ambiguous sample.
Here, we discuss how inter-class and intra-class GED relate to number invalid and overlapping samples. Let I be the set of all invalid samples, O the set of overlapping samples, and Ô = O \ I be the set of intra-class (valid) overlapping samples. Let C' be the lower bound the number of
14

---

Under review as a conference paper at ICLR 2022
invalid samples computed in Claim A.1 C is controlled by two parameters, D and r. We that whether samples are, on average, invalid or merely overlapping is dependent on the average distance between samples of different classes when I' is held constant. Clearly, when training, desire that I -> O, as this ensures the model mostly sees valid samples. We note that this ratio [
proportional to inter-class and intra-class distances as follows:
Recall that if A(z,) E E (D. sj --r-rr,)s - y, < 0 or equivalently, Dij < <T,+T for y, + y,-
Now, if ((x))) E Di < + j. for y; = Yj- Then, [Z] ~ (Dig < <T; + r)), y; # y, and
[0] 1 [D; < r; +i+T) fory: yj.
I(Dy<T;+Dy) for
1(D (D.g(T++Ty)..... for;; y;; O, when inter-class distance large for many samples, (i.e. the numerator is minimized), and when the intra-class distance is small for many samples (the denominator maximized). This suggests is desirable have a lower average intra-class distance and higher average inter-class distance.
Now,
While GED between samples cannot be controlled, the augmentation strength, r, can be controlled. It is desirable to minimize the number of invalid samples, while simultaneously maximizing the number valid (including overlapping) augmented samples as follows:
Min(C) s.t. max
Σ
[B()]
While the above optimization is intractable and assumes label information, it alludes two prop- erties critical to the success of contrastive learning: connectedness of samples and recoverabil- ity (HaoChen al., 2021). The number of invalid samples is indicative of the recoverability of different classes, while the above optimization indicates that we must also consider how well con- nected the augmentation sets are. We formalize this discussion in the next section.
A.1.3 GGA AND THE POPULATION AUGMENTATION GRAPH
The preceding section discusses the relationship between GGA, GED and error introduced by invalid samples. However, this analysis is method-agnoste and does not offer theoretical insights into graph contrastive learning.
In computer vision, recent attempts to analyze theoretically the performance of contrastive learning often assumes that sample views are independent, a condition clearly violated by data augmenta- tion (Arora et al. 2019 Tosh et al.) (021). To avoid this assumption, HaoChen et al. (2021) recently introduced the notion of a population augmentattinn graph (PAG), which represents augmented sam- ples as nodes and weighted edges as the likelihood of generating given pair of augmented samples from the same clean sample. Because samples from the same class are more likely to produce the same augmented sample than two random classes, connected subgraphs or communities in the PAG naturally correspond to underlying classes. HaoChen et al. (202T) designed and theoretically ana- lyzed a CL objective that performed spectral decomposition on the PAG to recover these subgraphs (classes). Using their proposed objective and the PAG, they were able to provide the first accuracy guarantees for CL.
We begin by defining the PAG and the assumptions critical to HaoChen et al. (2221)ss 's analysis. Then, we extend our analysis from the preceding section discuss how well these assumptions are supported for GCL.
Definition 4 (Population Augmentation Graph (HaoChen et al., 2021 ). Given a natural dataset X. let A(- [ be the distribution of augmentations given natural sample E, or, intuitively, as the probability of generating a particular augmented sample from the large but finite set of all possible augmented versions of Then, X == A A-
Let gP be the population augmentation graph, where all N samples in X form the nodes and W E RNN is the corresponding adjacency matrix. The edge weight between two nodes and x! is defined as
Waaa = (aE
15

---

Under review as a conference paper at ICLR 2022
Intuitively, if wa.w is larger, it is relatively easier generate the augmented pair from the same natural sample.
Now, since graphs are discrete, the augmentation severity restricted and only one edit can be applied at a time, we can completely define the population augmentation graph. Specifically, by using Remark [A.I] the entire set of allowable augmentations can be determined. Moreover, re- call that augmentations are performed randomly. Therefore, any A(x = BBa)) However, x' 7 B(I,), A(x(Z,) = 0 because it is not considered an allow- able augmentation for IG Note Wx,x' I E ,( E B(z,) for i + j. We refer to an edge whose endpoints are both overlapping sam- ples overlapping edge. Similarly, node in the PAG that is overlapping sample is referred
B(,,) is equally likely, so
T [B when x, x' are both overlapping samples, i.c.
to as an overlapping node. As such, we have defined all possible nodes in GP as well as how the edges are defined.
A.1.4 EXPLORING PAG STRUCTURE
Claim A.2. (Node Degree) Let be overlapping node in the PAG. Additionally, suppose there is an alternative PAG, where & is no longer an overlapping node but otherwise the PAG is the same. Then, will have larger degree than T. This is true even if &
an overlapping edge.
Proof. Because x is overlapping node, E B(I,) A E B(I,) for some i + j. Then, W2 = Ex' Wzs' = EXEBE, Wez'' + +I West Now, the alternative PAG, &. is not an overlapping node, so ã E B(x)) AI B(x;). & Then wy = Ex War' =I' Wazt- Clearly, Wa wa. This that if sample is overlapping node, it will have a higher degree than if the same sample were not an overlapping node.
Claim A.3 (GED Influences PAG structure). If data points x, x! share an edge the PAG, then max (GE T.), (ED(x',x.)) < max V.l.
Proof. Way 0 if and only if z e B(T,) Ax' l B(z.). Recall in Def. [ that e B(T,) if and only GEGD((, 2.) < max max(>]V,), +E and similarly for x'.
Moreover, edge weights and node degrees are also influenced by the GED between samples. Over- lapping edges can increase the weight between nodes. However, as discussed above, this requires that both ends of the edge are overlapping nodes. Definition 2 and Remark 3 we show how GED can be used determine the existence of such nodes. This further demonstrates the structure of the PAG is directly influenced by the GED between samples in X.
We emphasize that our analysis suggests that practitioners may be using generic graph augmen- tations without realizing that they are implicitly assuming that GED is a useful metric for their problem.
Having elucidated the structure of the PAG and its relationships to GED, we discuss how its struc- ture relates to the assumptions made by HaoChen al. (2021) when analyzing the PAG. Namely, they require that the PAG "cannot be partitioned into too many disconnected sub-graphs", and that "labels are recoverable from augmentations." " Indeed, their resulting bound on the error of spectral contrastive learning on the PAG depends upon the sparsest m-partition and classifier error.
The following assumption is from HaoChen et al. 2021)
Assumption 1. (Labels are recoverable from augmentations). Let Px and ys be its label. Let the augmentation x ~ A(- Ø). We assume that there exists a classifier g that can predict ya given with error at most That is, g(x) yz with probability least
Claim A.4. (Recoverubiliiy is lower-bounded by the number of invalid samples). a (Assumption) 7 can be lower-bounded when when (z)) contains an invalid sample: a 2 B(z) |
1 where
where Y is the set of labels represented among the natural samples that may have generated x.
Proof. For this claim, we first discuss the best error that can be expected when classifying an invalid sample, and then discuss the likelihood of encountering such sample given some Let x be an
16

---

Under review as a conference paper at ICLR 2022
invalid sample that can be generated from natural samples: X (z,).,,..... (Tx, )) Clearly, a's label is not well defined as it could be assigned any label ÿ E Y. However, the classifier g. is assumed to predict g(x) Yu, Vz, X with error most a. Then, the minimum error for such a classifier is 1 1ọ7 since the classifier does not know which natural sample generated x. For the remainder of the proof, we assume that g can correctly classify all samples expect invalid samples to derive a lower bound.
Having established the minimum error of a classifier on an invalid sample, we determine how likely g is to encounter such sample given F. Note that by assuming that g can correctly identify all other augmented samples, the classifier error is only incurred when is an invalid sample. Through Remark 3 we first determine if an invalid sample is possible given particular z. If an invalid sample possible, recall that every sample in the augmentation set, (x)) is equally likely by definition of generic graph augmentations. Therefore, the likelihood of generating I given E is
[B]]]] where the size of the augmentation set can be determined using Remark A.I] We note that could not provide an exact likelihood here because we assume (i) isomorphic graphs are counted separately and (ii) there is only one invalid sample in B(x:), when in practice there may be multiple invalid samples. Nonetheless, we are able to derive a lower-bound on the error of the classifier, g. given a particular J. by considering the likelihood of encountering an invalid sample and the error such 1 sample incurs: B((r) [ I a. While the above analysis focus on particular I, we can extend
1
the analysis to consider all samples, if we establish the likelihood of selecting natural sample that can produce an invalid sample. Jubsubbbuseni 1.1.2 for related discussion.)
L
Lastly, we hypothesize that GED can be related to the Dirichlet conductance of the PAG, where Dirichlet conductance measures how many edges cross between a subset, S, and its complement relative to the total number of edges in the subset. We discuss our intuition in the following simple example, but leave a rigorous mathematical discussion to future work. Let X' be dataset such that min;yy GED( æT)= > max(T), i.e the minimum distance between any two samples in the dataset is greater than the maximum allowable edits. Then, clearly the PAG contains [ fully connected subgraphs (cliques) that correspond to (z)), where Wzzz' [B() for x, x' E B(z). Given the struc-
ture of the graph, the conductance minimized when S B(7). as all edges within the subset are already contained. There by construction. We suspect that this observation can be extended to understand the behavior of the
edges to the complement because there are overlapping samples
sparsest m- partition of the PAG, which HaoCChe et al. (2021 use in their error bounds, but we leave that analysis to future work.
A.2 DATASET GENERATION AND EXPERIMENTAL DETAILS
Content Motifs
Class: A
Class: B
Class:
Class: D
Class: E
Class: F
Figure 5: Motifs used determine class labels.
We use the motifs shown in Fig. A.2 to define a 6 class graph classification task. It is important to ensure that the motifs are not isomorphic, as many GNNs are less expressive than the I-Weisfeiler Lehman's 's test for isomorphism (Xu et al. (2019). ). For each class, 1000 random samples are gen- erated as follows: (i) We randomly select between 1-3 motifs be in each sample. At this time, motifs all belong to the same class, though this condition could easily be changed for more difficult task. (ii) We define the number of content nodes, C., as the size of the selected motif, scaled by the number of motifs in the sample. (iii) For given style ratio, we determine the number of possi- ble style nodes as S, = PC, (iv). We define RBG((n) using networkx's 's random tree generator:
17

---

Under review as a conference paper at ICLR 2022
networkx. generators. trees. random tree. We note that other random graph genera- tors would also be well suited for this task. (v) For additional randomness, we create background graphs using S, 2, and also randomly perturb up-to 10% of edges in sample. We repeat this set-up with p E (0.5, 1.0, 1.5, 2.0, 3.03 to generate the datasets used in Sec
Experimental Set-up: We follow You al. (2020a) for TUDataset experiments. We use 5-layer GIN model with sum pooling for all synthetic experiments. Models are pretrained for 100 epochs and then fine-tuned for 200 epochs with I learning rate drop when the loss plateaus. The hidden layer dimension is 32. We concatenate hidden representations for a representation dimension of 160. All models are trained with Adam, 0.001. For the sample complexity experiment, we allow for end to end training. For all other experiments, we freeze the backbone and only train the linear prediction head.
A.3 INDUCTIVE BIAS, ADDITIONAL RESULTS
To further demonstrate the effectiveness of untrained models on popular benchmarks, we include results from different GNN architectures: GraphSage (Hamilton et al. (2017). PNA (Corso et al. (2020) ) GCN (Kipt & Welling (2017)) and GAT (Velickovic et al. (2018)). We note that while it has been informally discussed that untrained GNNs have a strong inductive bias, our intention to formalize why these untrained models must be included when evaluating unsupervised graph representation learning. Moreover, in Tab. A.4, we include variant of untrained models, where we initialize BatchNorm statisties without computing any gradients by iterating over the dataset once. For several datasets and baselines, we see that this Warmup step makes the untrained baseline even stronger. We believe that future work should also consider this simple baseline when evaluating the performance of their models.
Table 3: Inductive Bias.
GraphSAGE
Layer
4 Layer
5 Layer
GraphCI.
InfoGraph
MUTAG
0.85 = 0.005
0.85 0.006
0.85 = 0.005
0.82 = 0.040
0.85 = 0.005
PROTEINS
0.004
0.003
0.74 0.005
0.75 1 0.002
0.74 = 0.008
NCI1
0.74
0.75
0.73 : 0.011
0.78 - 0.000
0.79 = 0.002
DD
0.706
0.78 + 0.002
0.78 = 0.005
0.80
0.008
0.77 = 0.010
REDDIT-B
0.85 0.014
0.83
0.83 0.005
0.66 0.137
IMDB-B
0.66 + 0.012
0.81 + 0.008
0.81 + 0.008
PNA
Layer
4 Layer
Layer
GraphCL
InfoGraph
MUTAG
0.88 0.88 0.011
0.89 +: 0.009
0.86 :: 0.023
0.90 + 0.014
PROTEINS
0.70
0.012
0.74 = 0.005
0.047
0.74 0.003
NCTI
0.67 0.008
0
0.68 + 0.010
0.008
0.77 = 0.019
DD
0.764
0.76 + 0.002
0.76 + 0.008
0.76 0.006
REDDIT-B
0.90 0.003
0.88 0.014
0.89 1 0.010
0.92 1 0.006
0.02 0.006
IMDB-B
0.72 0.007
0.68 0.011
0.68 1: 0.010
0.71 0.009
0.71 0.009
GCN
Layer
4 Layer
Layer
GraphCL
InfoGraph
MUTAG
0.85 + 0.003
0.85 0.004
0.85 + 0.005
0.82 0.013
0.85 0.003
PROTEINS
0.0003
0.007
0.74 0.004
0.75
1.000:0004
0.75 : 0.003
NCI1
0.76 0.004
0.001
0.75 1 0.002
0.78
0.79 - 0.007
DD
1.88200002
0.78 + 0.003
0.007
0.76 = 0.003
REDDIT-B
0.52 0.005
0.51 + 0.003
0.52 + 0.005
0.92
0.80 0.062
IMDB-B
0.54 0.001
0.07
0.58 0.008
0.01
0.62 0.070
GAT
Layer
4 Layer
Layer
GraphCL.
InfoGraph
MUTAG
0.84 0.003
0.85 0.009
0.84 + 0.003
0.81 0.032
0.85 - 0.013
PROTEINS
0.74
0.74
0.74 0.006
0.007
0.74 0.005
NCII
0.76 0.009
0.00
0.76 0.002
0.78
0.70 = 0.040
DD
0.78 +: 0.005
0.77
0.79 + 0.001
0.76 = 0.005
REDDIT-B
0.52 + 0.005
0.53 + 0.004
0.52 + 0.012
0.75 1.7++00000 0.004
IMDB-B
0.51 0.004
0.009
0.50 1: 0.005
0.51 0.007
A.4 INVARIANCE, ADDITIONAL RESULTS
We extend representation invariance results on standard benchmarks to different architectures below in Tab. A.4 As our main results, we use random subgraph sampling and node drop- ping our augmentations, following You et al. 20000a, when computing invariance. We find that
18

---

Under review as a conference paper at ICLR 2022
similar trends hold: while training with GCL does improve performance and invariance somewhat, untrained models perform comparably without the same levels of invariance.
Table Invariance Table.
RandGAT
(Acc)
WarmupGAT
(Acc)
GAT (GraphCL)
(Acc)
MUTAG
0.993
0.843
0.364
0.793
0.608
0.807
PROTEINS
0.987
0.737
0.819
0.738
0.554
0,744
NCII
0.993
0.761
0,543
0.771
0.669
0.781
DD
0.970
0.779
0,381
0,778
0.361
0.793
REDDIT-B
1,000
0.517
0,850
0.724
0,982
0.747
IMDB-B
1.000
0.512
0.979
0.670
0.994
0.512
RandGIN
(Acc)
WarmupGIN
(Acc)
GIN (GraphCLL
(Acc)
MUTAG
0.921
0.867
0,208
0.866
0.852
0.868
PROTHINS
0.910
0.745
0.495
0.750
0.547
0.744
NCII
0.921
0.707
0,281
0.769
0.768
0.778
DD
0.907
0.732
0,071
0.760
0.638
0.786
REDDIT-B
0,906
0.723
0.242
0.768
0.286
0.895
IMDB-B
0.914
0.672
0.791
0.700
0.468
0.711
RandGCN
(Acc)
WarmupGCN
GCN (GraphCL)
(Acc)
MUTAG
0.996
0.847
0.491
0.807
0.561
0.821
PROTEINS
0,980
0.739
0.886
0.750
0.765
0.749
NCII
0.991
0.756
0,480
0.767
0.664
0.780
DD
0.968
0.779
0.440
0.772
0.367
0,789
REDDIT-B
0.999
0.519
0.129
0.833
0.678
0.919
IMDB-B
0.914
0.540
0.539
0.833
0.994
0.709
RandSAGE
(Acc)
WarmupSAGIE
(Aec)
SAGE (GraphCL)
(Acc)
MUTAG
0,910
0.846
0.273
0,801
0.303
0.823
PROTHINS
0.907
0.732
0.582
0.747
0.507
0.749
NCI1
0.912
0.737
0.412
0.771
0.579
0.779
DD
0.590
0.771
0.590
0.781
0.727
0.801
REDDIT-B
0.833
0.849
0.225
0.740
IMDB-B
0.223
0.663
0.223
0.497
A.5 DATASET STATISTICS
A.6 RELATED WORK
Augmentations for graphs are difficult to define due to their discrete, non-euclidean nature. Furthermore, unlike images or natural language where there an intuitive understanding of what changes will preserve task-relevant information, such understanding exists for graphs. Indeed, a single edge change can completely change the properties a molecular graph. Therefore, only a few works consider graph data augmentation. Zhao et al. (2020) note that node classification task can be perfectly solved edges only exist between same class samples. They train neural edge predictor be of the same class and break edges between nodes of expected dissimilar classes. However, this approach expensive and not applicable to graph classification. Kong al.) (2020) argue that information preserving topological transformations are difficult for the aforementioned reasons and instead focus feature augmentations. Throughout training, they add adversarial perturbation to node features to improve generalization. To avoid incurring the large expense of adversarial training, they leverage [Shafahi et al. (2019) and compute the gradient of the model weights while computing the gradients of the adversarial perturbation. This approach is not directly applicable to contrastive learning, where label information cannot be used generate the adversarial perturbation.
Graph Data Augmentation:
increase homophily by adding edges between nodes expected to
Graph Self-Supervised Learning: Several paradigms for self-supervised learning in graphs have been recently explored, including the use of pre-text tasks, multi-tasks, and unsupervised learning. See Liu et al. (2021) for up-to-date survey. Graph pre-text tasks often reminiscent of image in-painting tasks Yu et al. (2018), and seek to complete masked graphs and/or node features (You et al. (2020b); Hu et al. (2)((22) (2020). Other successful approaches include predicting graph level prop- erty level properties during pre-training or part of regular training to prevent over-fitting (Hu et al.) 2020 These tasks often must be carefully selected to avoid negative transfer between tasks. Many
19

---

Under review as a conference paper at ICLR 2022
Table 5: Dataset Description
Name
Graphs Classes Avg. Nodes Avg.
Edges
Domain
IMDB-BINARY Yanardag & Vishwanathan 2015
1000)
2
19.77
96.53
Social
REDDIT-BINARY Yanardag & Vishwanathan 2015
2000
429.63
497.75
Social
MUTAG Kriege
Mulzel 2011 2012
188
17.93
19.79
Molecule
PROTHINS (Borgwardr et al. 2005
1113
39.06
72.82
Bioinf.
DD Shervashidze al. |011
284.32
715.66
Bioinf.
NCII Wale & Karypis, 2006
4110
29.87
32.30 Molecule
Table 6: Selected Graph Contrastive Learning Frameworks. Brief description of augmentations used by selected frameworks is provided. Most frameworks use random corruptive, sampling, or diffusion-based ap- proaches generate augmentations.
Method
Augmentations
GraphCL You et al. (2020a))
Node Dropping, Edge Adding/Dropping, Attr. Mask- ing, Subgraph Extraction
GCC Qiu et al. 2020)
RWR Subgraph Extraction of Ego Network
MVGKL Hassan Ahmadi 2020
PPR Diffusion + Sampling
GCA (Zhu al. 2020))
Edge Dropping. Attr. Masking (both weighted by cen- trality)
BGRL Thakoor et al 2021
Edge Dropping, Attr. Masking
SelfGNN (eettto Girdzijuusks (022))
Attr. Splitting, Attr. Standardization + Scaling, Local
Degree Profile, Paste Local Degree Profile
unsupervised approaches have also been proposed. [Snn et al. (2020); Velickovic et al. (2019) draw inspiration from Hjelm et al. (2019) and maximize the mutual information between global and local representations. MVGRL (Hassani & Ahmadi (2020)) contrasts different views at multiple granu- (2018). You al. (2020a): Qiu et al. (2020): Zhu et al. (2020);
larities similar to van den Oord Thakoor et al. (0 & Girdzijauskas (2021) use augmentations to generate views for con- trastive learning. See Table A.6 for a summary of the augmentations used. We note that random corruption, sampling or diffusion based approaches often do not preserve task relevant information or introduce meaningful invariances.
20


Reviews:
[{"review_id": "j73TxHqnBo", "reviewer": "Reviewer_UMWA", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Strengths: The motivation of this paper is relatively new. Data augmentation in graph contrastive learning is an important part which is often overlooked by researchers. It is a successful transfer of work from CV and can show that the author has a deep understanding of the latest work on CV contrastive learning. The benchmark design based on motif and the design of \"STYLE VS. CONTENT\" on the graph are both highlights.\n\nWeaknesses: The analysis of the relationship between graph contrastive learning effective conditions and data augmentation is not theoretical enough. Some sentences confused me when reading such as \"To define a min-cut partition, the number of edges crossing a subset of nodes should be minimized while the number of edges within a subset should be high\". It would be better if the theoretical analysis part was supplemented in more detail. The problem and process of analysis in Section 3.2 is too hand-waving.\nSecondly, I think your experiment with GNN without training is controversial in Table 1. If you follow the training mode of graph contrastive learning (first defined in DGI), the untrained GNN is combined with a trained downstream linear layer. I think the existence of this linear layer is not enough to support your conclusion that untrained GNN is competitive. If you insist on proving this statement, please use the results of the clustering experiment which can be found in MVGRL. \nFinally, I think the contribution of the paper is not enough. Although the analysis and motivation are new, they are still used from CV. The design of benchmark and \"STYLE VS. CONTENT\" is novel but simple. I think it is a relatively complete work to propose a better data augmentation or sampling method on this benchmark based on the riched theory.\n", "summary_of_the_paper": "This paper focuses on the augmentation of graph contrastive learning. Authors make further explorations on graph contrastive learning based on the previous CV contrastive work (HaoChen et al. (2021) ) and hope to design a good benchmark by analyzing the relationship between GCL/auto-encoding methods and augmentations. In the analysis part, authors mainly use the perspective of population augmentation graph work to find connections with existing graph augmentations (mainly You et al., 2020a) and analyze the relationship between GED and task performance/downstream labels. In the benchmark part, authors proposes a benchmark based on the idea of \"STYLE VS. CONTENT\" which is inherited from CV contrastive work. The analysis of the experimental results is okay.\n", "summary_of_the_review": "The motivation of the article is good, but I have some problems in terms of contribution and theoretical analysis. Experiment and analysis are okay.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "QmnQt_61F85", "reviewer": "Reviewer_MoyX", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "One of the claimed contributions is the “theoretical analysis of when contrastive learning is expected to work well”. However, in section 3.2, there is no link of the “fixed error” of the contrastive learning performance to the graph properties.  \n\nA conclusion is made from Fig 1 (a), “the learning invariance was not necessary for downstream task performance”.  However, there does exist performance (accuracy) improvement on dataset of IMDB-BINARY and NCI1.  It would be more valuable to study the necessarity of learning invariance on different types of graphs, and how this necessarity depends on what kinds of graph properties. \n\nAnother difficulty is found in understanding the claimed contribution to “identify a style vs. content trade-off in graphs and introduce an extensive benchmark setup that can carefully control this trade-off”.  Section 5 did analysis of style (irrelevant information) vs. content (task relevant information). However, it is still unclear about how to identify a trade-off parameter in a given application problem. \n\nMore details should be given about datasets PROTEINS in evaluation, same for  MUTAG, IMDB-BINARY and IMDB-BINARY.\n\n", "summary_of_the_paper": "This paper targets on investigating the role of dataset properties and augmentation strategies on the success of graph contrastive learning and reconstruction-based approaches.", "summary_of_the_review": "The paper works on an interesting and valuable problem. However, the analysis results are not strong enough to support the claimed contributions.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Fs7op8mx3R-", "reviewer": "Reviewer_UyEA", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Recently, we have witnessed an explosive development of self-supervised graph learning methods. As one of the most import parts, data augmentation technology provides a flexible way to generate training set without the high-cost labels. Many works draw lessons from the computer vision community and design a bunch of methods to generate the augmented views for contrastive learning graph representations. However, it's still not clear why and to what extent the data-augmentation methods have positive benefits for directing the graph neural models to the right way. There're some works trying to uncover the mystery by studying the contrastive loss, but rare attention being paid to the impact of the graph augmentation. While this work seems to be a pilot study about the condition when contrastive graph learning can work well. From the manuscript, we can see that authors present the relation between graph edit distance and augmentation operations (e.g. dropping edges/nodes, adding edges/nodes), and claim that the performance of contrastive graph learning could be bounded by the graph edit distance (GED) between different classes. \n\nConcerns:\n1. The studied problem in this work is very important for the research community. However, the quality of the presentation make it difficult to understand the motivation behind. After checking the draft several times, it's still unclear why the GED can be a general criterion to judge the success of GraphCL with both node attributes and graph structure as the input data. As we know that GED is defined on the graph structure. I just wonder the generalizability of the claim raised by this work. Suppose that the GED has positive impact, the writing is difficult to follow. There're many claims which are copied from the previous work proposed by HaoChen et al.. While they are not organized logically, and the missing background knowledge makes some claims difficult to capture the logic behind. For example, what is the definition of spectral decomposition, which is presented in HaoChen et al. But it shows up in Section 3 without any explanation. \n\n2. Besides the discussion about the connection GED and GraphCL, the contribution of this work seems to be applied the augmentation method to reconstruction-based task like edge reconstruction. However, it seems not to be discussed in the main content until the section for presenting the experiment setting.\n\n", "summary_of_the_paper": "This paper attempts to study the connection between graph edit distance and the reason behind the success of self-supervised graph learning. ", "summary_of_the_review": "Good research problem, but the presentation is not good enough to make the key idea clear.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "-ogxX2Yrti6", "reviewer": "Reviewer_97Kb", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper studies the success conditions of graph contractive learning (GCL) with generic graph augmentation (GGA) and claims the success depends on the graph edit distance between classes. It empirically show that reconstruction-based approaches (GAE and AAGAE) perform well in low graph style regimes and GCL with GGA benefits from moderate style. \n\nThe problems investigated in the paper is interesting and is significant to the unsupervised graph representation learning community. However, their claims lack rigorous mathematical and empirical demonstrations. In addition, the analysis is restricted to spectral contractive loss functions, and it is not clear how to extend the analysis to general GCL approaches. Further, the experiments were conducted on relatively limited methods, and it is not clear whether the results are applicable to more general approaches.\n\n\n## Strength\n\n\n1.\tThe presentation is easy to follow.\n2.\tThe problem of identifying success conditions of graph contractive learning investigated in the paper is interesting.\n3.\tThe experimental results, i.e. the impacts of the ratio of style and content on the performance of GCL, GAE, and AAGAE, are interesting and may provide some insights to the unsupervised graph representation learning community.\n\n## Weakness  \n\n\n\n1. The claims of the paper mainly build  upon the theoretical results of a recent paper [1], whose details are omitted in the paper. Would be great to carefully discuss the relationship to the results of [1]\n2.  The analysis in Section 3 is restricted to PAG and the spectral contrastive loss and there are no illustrations to show how to extend the analysis to general GCL approaches.\n3. Additionally, the claim, that the success of GCL with GGA depends on the graph edit distance between classes, lacks rigorous mathematical and empirical evidence.\n4.  The experiments were conducted for only three methods (i.e., GCL, GAE, AAGAE) and the analysis of paper is restricted to GCL with GGA. There is no indication whether their results can be applied to general GCL approaches or other reconstruction-based approaches.\n", "summary_of_the_paper": "The paper studies the success conditions for graph contractive learning (GCL) with generic graph augmentation (GGA) and asserts that these conditions depend on the graph edit distance of samples within and across classes. Using empirical evidence, the authors demonstrate that reconstruction-based approaches (GAE and AAGAE) perform well at low graph style regimes, while GCL with GGA benefits from moderate graph style regimes.", "summary_of_the_review": "This paper studies an important open problem,  but is lack of rigorous mathematical demonstrations and has limited empirical studies.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this paper, data augmentation for graph contrastive learning (GraphCL) is studied. Most reviewers agree that the problems addressed in this paper are interesting and important for unsupervised graph representation learning literature. However, many reviewers were not fully satisfied with the novelty and the claim of the main contribution of this paper, a theoretical analysis of the conditions under which data augmentation works in GraphCL, due to the lack of clear explanation and evidence. Unfortunately, no reviewer has suggested acceptance of this paper at this time.
Decision: Reject