Analyzing Data-Centric Properties for Graph Contrastive Learning
Authors: Puja Trivedi
Ekdeep Singh Lubana
Mark Heimann
Danai Koutra
Jayaraman J. Thiagarajan
Venue: NeurIPS 2022 Accept (2022)
Keywords: unsupervised representation learning
generalization
graph neural networks
augmentation
invariance
contrastive learning
self supervised learning

Abstract: Recent analyses of self-supervised learning (SSL) find the following data-centric properties to be critical for learning good representations: invariance to task-irrelevant semantics, separability of classes in some latent space, and recoverability of labels from augmented samples. However, given their discrete, non-Euclidean nature, graph datasets and graph SSL methods are unlikely to satisfy these properties. This raises the question: how do graph SSL methods, such as contrastive learning (CL), work well? To systematically probe this question, we perform a generalization analysis for CL when using generic graph augmentations (GGAs), with a focus on data-centric properties. Our analysis yields formal insights into the limitations of GGAs and the necessity of task-relevant augmentations. As we empirically show, GGAs do not induce task-relevant invariances on common benchmark datasets, leading to only marginal gains over naive, untrained baselines. Our theory motivates a synthetic data generation process that enables control over task-relevant information and boasts pre-defined optimal augmentations. This flexible benchmark helps us identify yet unrecognized limitations in advanced augmentation techniques (e.g., automated methods). Overall, our work rigorously contextualizes, both empirically and theoretically, the effects of data-centric properties on augmentation strategies and learning paradigms for graph SSL. 

Analyzing Data-Centric Properties for Graph Contrastive Learning
Puja Trivedi
Ekdeep Singh Lubana University of Michigan CBS, Harvard University eslubana@umic ch. edu
Mark Heimann
University of Michigan puja anjjuimmmii ch. edu
Lawrence Livermore National Labs
heimann2011ni gov
Danai Koutra
Jayaraman J. Thiagarajan
Unversity of Michigan dkoutradumi ch. edu
Lawrence Livermore National Labs jjayarame1 am@lln1........mmmmmmmmmmmmmmm1m gov
Abstract
Recent analyses of self-supervised learning (SSL.) find the following data-centric properties to be critical for learning good representations: invariance to task- irrelevant semantics, separability of classes some latent space, and recoverabilityy of labels from augmented samples. However, given their discrete, non-Euclidean nature, graph datasets and graph SSL methods are unlikely to satisfy these prop- erties. This raises the question: how do graph SSL methods, such as contrastive learning (CL), work well? To systematically probe this question, we perform a generalization analysis for CL when using generic graph augmentations (GGAs), with focus on data-centric properties. Our analysis yields formal insights into the limitations of GGAs and the necessity of task-relevant augmentations. As we empirically show, GGAs do not induce task-relevant invariances on common benchmark datasets, leading to only marginal gains over naive, untrained basclines. Our theory motivates synthetic data generation process that enables control over task-relevant information and boasts pre-defined optimal augmentations. This flexible benchmark helps us identify yet unrecognized limitations in advanced augmentation techniques (e.g.. automated methods). Overall, work rigor- ously contextualizes, both empirically and theoretically, the effects data-centric properties augmentation strategies and learning paradigms for graph SSL.]
Introduction
Self-supervised learning (SSL) 1.9 has revolutionized visual representation learning by producing
representations that are more robust 10 [1] transferable 12 13 and semantically consistent K
than their supervised counterparts. This impressive empirical success has motivated surge of efforts that seek to gain insights into SSL's behavior 14,211 or adapt successful frameworks to different Notably, many analyses of SSL have converged upon the following data-cent cettaccentiic properties as critical to its success: (i) augmentations should induce invariance to task-irrelevant attributes, as better reflect the underlying data generation process and improve generalizability; (ii) samples (and corresponding augmentations) from different underlying classes should be separable in some latent space, as to ensure a -erffrrrro classifier is realizable; and (iii) labels of augmented samples should be recoverable from the natural sample using which they so that representations are semantically consistent for downstream tasks.
modalities, including graph data 22 26
were generated [6 20 27
Correspondence to pujat aetiiccuccc...m edu.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Due to the continuous representation of natural images and well-designed augmentation strategies, these properties are indeed aligned with standard visual SSL practices [8
However, despite the growing popularity of SSL for graph representation learning, it appears unlikely that the above properties are supported for non-Fuclidean, discrete data. Indeed, the design of recoverable graph data augmentation [22)31] remains an open research area because is it difficult to determine prima facie what changes a graph's topology or node features will preserve semantics. Moreover, as graphs are often abstract representations of structured data, it is also unclear what invariances are relevant to the downstream task. The assumption of a separable latent space may also be violated as intermediate points in this latent space may be meaningless in the discrete, structured input space. In contrast to natural image data, the systematic evaluation of these properties for graph SSL is difficult as it must accommodate both discrete and structured data.
Our Work. Better understanding the relationship between graph SSL practices and the aforementioned properties can help explain the behavior of existing frameworks and inform the design of new ones. Therefore, in this work, we take the first step by analyzing commonly used generic graph augmentations (GGAs) and designing useful tools that enable probing of these properties, including a theoretical framework and synthetic data generation process that helps disentangle the effects of unrecoverable augmentations from performance. Our contributions can be summarized as follows:
Sec. 3 Analysis of Generalization and Separability. We provide the first generalization error bound for graph CL when using GGAs, demonstrating that GGAs can induce a performaacc-sspaaabbiiy trade-off that is determined by underlying dataset properties (see Figure Ip.
Sec. 4.1:
Missing Invariance on Benchmark Datasets. On standard benchmarks, we show that models trained with GGAs have marginal improvements in accuracy and induce limited task-relevant invariance, at best, when compared to untrained encoders. We thus reveal a fundamental misalignment between the objectives and practical behavior of graph CL (see |Figure 2).
Synthetic Data Generation Process. We propose a synthetic data generation process that allows for control over augmentation recoverability and dataset separability (see Figure 3). Using this process, we validate our theoretical observations and demonstrate that recently proposed automated and implicit augmentation methods struggle to induce task-relevant invariances (see Figure 4).
Sec. 4.2
2 Background
In this section, we briefly discuss existing graph SSL paradigms. (Please see App. G for additional discussion.) We then discuss the motivation behind data-centric properties (task-relevant invariance, separability and recoverabilty) central to this work.
Self-Supervised Graph Representation Learning. Recent advancements in representation learning have been driven by the SSL paradigm, where the goal is to ensure representations have high similarity between positive views of a sample and high dissimilarity between negative views. Existing SSL frameworks can be broadly categorized based on the mechanism adopted for enforcing this
31 (2), such as GraphCL [2], use and BGRL 24 use Siamese architectures with stop gradient 22 and asymmetric branches (21] respectively; SpecCL [5 uses a spectral clustering loss (SpecLoss) to enforce consistency; others attempt to directly reduce redundancy between views 33). Despite these differences, all methods rely upon data augmentation to generate positive views, which are assumed to share semantics. Generic graph augmentations (GGAs) [22 are a popular strategy and assume limited changes to a graph's node features or topology are unlikely to alter its label. GGAs include random node dropping, edge perturbation, masking node attributes and sampling subgraphs. Other strategies include using diffusion matrices 23 GGAs with a non-uniform prior, automated methods which rely upon bivee optimization [29 or adversarial optimization [II, and implicit methods, such as SimGRACE [3)],
consistency: contrastive learning (CL) frameworks I N 7 29
the InfoNCE loss; approaches that rely only on positive pairs, such as SimSiam
which use weight-space perturbations as augmentations. Here, we primarily focus on GGAs due to their popularity, simplicity and effectiveness. Please see App. G for additional discussion about augmentation paradigms.
Theoretical Analsyis of SSL. Several different perspectives have recently been used to successfully
analyze SSL's behavior, including learning theory 15 14
causality [18 17, information
theory 27 and loss landscapes (5) Many of these analyses assume, either implicitly [8 34 or

---

explicitly 15 28 39 40
the existence of a latent space that is invariant to augmentation functions and supports the properties of recoverabilityy and separability (also see Segure
Invariance to Augmentations: Producing similar representations for positive views, i.e., augmenta- tions, induces invariance to the corresponding transformation function. Indeed, if augmentations are related by properties that are not relevant to the downstream task, representations will become invariant to this relationship over the course of SSL training and generalization will improve A1 16 Conversely, however, if augmentations induce invariance to relevant properties, then representations will fail to represent this information and are likely to lose task performance (e.g, color invariance is harmful when classifying different Labradors) 20 42). This latter point is often ignored by the theoretical analyses mentioned above. We note Tian et al.' 's information theoretic framework [[6] is a notable exception to this critique; we discuss the limitations of their results in App.
Recoverability and Separability: These properties state that in the latent space which instantiates the data generation process, two augmentations of a sample are close to each other (e.g. a clear and blurry dog) and unrelated points (e.g.. dogs and cats) are sufficiently separated from each other. is often implicitly assumed that only task-relevant augmentations are allowed [5 (28) While originally proposed for manifolds (3)), both recoverability and separability have been recently converted to graph connectivity properties [15 and verified empirically on modern deep learning methods [2]] Specifically, recoverability and separability can be used to bound generalization error on unseen data and we demonstrate how this can be done for graph CL in Sec.
Notations. Let X be natural dataset with r different classes. Our use of word natural implies the samples in this dataset were collected via natural sensing process (e.g., molecules from wet-lab experiments or scene graphs from images). We use A(.Ig) to denote the distribution of augmentations for the sample g E X. Here, A(glg) represents the probability of generating a particular augmentation g. and X := x is the set of all samples transformed via our set of augmentation functions. Let f x X + Rd be a feature extractor, where fx) can be used for downstream tasks. Unless otherwise noted, let g be natural (graph) sample from X, A(-I-) be some GGA, and ~ AA-ll) be an augmented graph generated using given GGA. V/ and Eg correspond, respectively, to the node and edge sets of g. We note our generalization analysis will specifically focus on the recently proposed contrastive loss by HaoChen et al. [[3], called SpecLoss (C()). which we define as follows: let ~ A(- (g). g+ ~ A(-lg), given g E X, and g ~ A(' given g' Px A g' + T. Then, for the positive/negative pairs (g. (7.gt), / // ). SpecLoss is: C()) - Bg ( [(g+)] +
[ ((g)))(())))))))))))) } In a contemporary work, Saunshi al. 1 II developed a generalization analysis for general contrastive loss functionals, including Loss Our analysis has a similar algorithmic flow as Saunshi et al.'s and hence the takeaways from our work can be easily extended for other contrastive methods as well. We provide additional discussion of this extension in App. C.T
3 Generalization Bounds for CL with GGA
As discussed above, recent analyses have found that SSL generalization error can be bounded under the assumptions of invariance to relevant augmentations, recoverability, and separability. In this section, we demonstrate how GGAs influence these properties by deriving a generalization bound tailored for graph data. Notably, this bound allows to demonstrate conditions where using GGAs results in low separability and recoverability, motivating the need for augmentations that induce task-relevant invariances that go beyond generic perturbative graph transformations.
Key Insight: Our main idea for the following analysis is that GGAs can be instantiated in a general manner as a composition of graph edit operations. This allows us to derive a unifying assumption related to recoverability and separability in terms of the graph edit distance (GED) between samples. Moreover, because GED amongst samples is property intrinsic to the dataset, we can now discuss how the tightness of a SSL generalization error bound (SpecLoss's s, specifically) will change as a function of GED between samples of underlying classes and augmentation strength.
We begin by defining GED and explaining how GGAs can be represented using graph edit operators.
Definition 3.1 (Graph Edit Distance). Let the elementary graph operators comprise the set of graph edits: these include node insertion, node deletion, edge deletion, edge addition, and an additional
3

---

Class:
Class:
Inconsistent Samples
Natural
Separable Class
Sample
Manifolds
(Recoverable) Augmented Samples
Figure 1: Illustrating data-centric properties forming the core of our assumptions. Our generalization analysis (Sec. (3) relies upon several data-centric properties. namely recoverabilityy, separability. and frequency of inconsistent samples. Here, we illustrate these properties via figure. (i) Separability: Samples from different classes should be separable, as illustrated by the existence of separate manifolds for different classes. This property helps assume the existence of a classifier that can classify natural samples with low error. (ii) Recoverability: Labels augmented samples should be recoverable from the original samples from which they were generated. This entails that augmentations generated from the same original samples are expected to be closer in latent space than two arbitrary samples, which will likely correspond to different classes. This property helps assume constraint the classifier h that it must also classify the augmentations of sample the same class as that the sample. (iii) Inconsistent Samples: While the likelihood generating augmentations that alter class semantics is low for image data, this if often note the case in graphs, especially when using generic graph augmentations. We refer to augmentations that can be generated from original samples belonging to different classes inconsistent, and demonstrate that graph edit distance be used to identify such samples. Overall, our theory shows inconsistent samples decrease separability and recoverability, harming generalization. (Figure inspired from Chung et al. 3 and HaoChen et al. 15
categorical feature replacement operator. Then, GED (91, 92) min (E) PP (91)92) E c (e,). where P (g1, 92) is the set of paths (series of edit operations) that transforms graph 91 be isomorphic to graph 92. Here, e is i-th edit operation in the path, and c(e;) is the cost for performing the edit.
As shown Table I frequently used GGA transforms can be easily decomposed using standard graph edit operators described in Def. 3.1. For example, assuming each operator has unit cost, the edge perturbation augmentation can be seen as applying the minimum cost path consisting of edge deletion and edge addition operations obtain g from g. Further, augmentation strength and the set of possible augmentations for a given natural sample can also be expressed in terms of GED:
Lemma 3.2. Allowable augmentations can be expressed using GED. Let represent augmentation
strength or the fraction of the graph that GGAs may modify. Then, E {1> | lt repre- sents the number of discrete. allowable modifications for the specified GGA, so GED S 8. Correspondingly, we have g A(g) + GED( g 8.
For example, consider a graph g ~ A( g), generated via node dropping. Then, 9 contains 1 8 nodes and the minimum cost path to transform g to g contains only 5 "node deletion" operations. Further, all augmen- tations generated from g will have 1 5 nodes and thus have GED 9) S 8. In Appendix D we prove the above statement and demonstrate how to approximate AAg)) (e.g., the of allowable augmentations for given natural sample) using a combinatorial, counting
Table 1: Generic Graph Augmentations vs.
Graph Edit Operators. GGAs can be straight- forwardly expressed using graph edit operators. Please see Appendix D for a detailed discussion.
Angmentations
Graph Operators
Node Dropping
Deletion
Edge Perturhation
Edge Deletion, Edge Addition
Categorical Attribute Masking
Feature Masking Operator
Sub graph Sampling
Node Deletions
procedure that is dependent on 8. Because GGAs are applied randomly, note that the probability of
generating a particular augmentation is A(glī) R [Alii] Given these definitions, we now derive unifying assumption in terms of GED between samples. We begin by formally introducing the separability and recoverability assumptions, focusing on the recently proposed, unified version [5]
Assumption 3.3 (Separabilityy plus Recoverability Assumption, (Assm. 3.5 in 15)). Let E X and v()) be label, and g ~ A(-Ig). Assume that there exists a classifier h, such that h(g) = v(g) with probability least 1 a. We refer to a as the error of h.

---

visualization explaining this assumption. Intuitively, Assm. 3.3 states that there must exist a classifier h that able to associate sample's label with its augmentations, hence enabling recoverabilityy i.e., representations of augmentations are close to each other. Meanwhile, by ensuring augmentations of samples from class with label "A" are classified as "A" and from class with label "B" are classified as "B", the assumption simultaneously enables separability, i.e., representations of samples from different classes should be dissimilar. As we will see, the generalization bound will be function of the probability that a classifier satisfying Assm. 3.3 associates augmentations of class's s samples with another class, As a grows larger, the generalization error bound becomes less tight. Therefore, it is important to understand how the choice of augmentation and augmentation strength (7) can influence the error of h. We show one can also understand a as a trade-off between inter-class GED of samples and augmentation strength.
See Figure
Intuitively, h will incur error on augmented samples that can generated from a set of natural samples that belong to different underlying classes, as it is unclear how these samples should be embedded in latent space. We now formally define such samples. First, using Lemma 3.2 determine if two augmentations could have been generated from the same sample.
we can
Corollary 3.4. (Co-occuring augmentations.) Let X and g.g' E X. Then, A(g) ^g' A(g)= + GED(g.g) g') S 25, where 8 = min min(1>) ([>VV L Lr/Vll) Ly|Eg]]}.
Given the above result, we now define inconsistent samples as follows.
Definition 3.5 (Inconsistent Samples). Let g E X, and y X - r be a labeling function. Further, let F = [glg E X A GED g) s 6} be the set of natural samples that may have generated g and } be the set of unique labels. If g is an inconsistent sample, |M > 1.
Y. = وg(g)g E }n
Essentially, if two augmentations co-occur (see Corr. 3.4 from two or more different natural samples, such that the samples do not share the same underlying label, we refer to such samples as inconsistent (also see Figure 1). Now, we assume the behavior of h on inconsistent samples is fixed such that h(g) = y, for some fixed y E V%% This allows us to use to induce a r-way partition over X, such that each sample, g. belongs to a partition, (g). Further, because h incurs error on inconsistent samples, a can be lower bounded by the ratio of inconsistent to total samples. To this end, we use GED to identify inconsistent samples by identifying disagreement amongst partitions as follows.
Lemma 3.6 (Using GED to identify inconsistent samples). Let g, E X and GED(g,g) g') S 28 such that g E S; g' E Sj and + j. where partitions are induced by h. Then, at least one ğ E (g.g') must be an inconsistent sample.
Note that the above lemma does not rely ground-truth label information to identify inconsistent samples, but only GED from natural samples. Given that the error on inconsistent samples is irreducible, as it is unclear which y Y.. is correct, we can lower bound the error of h follows: Corollary 3.7 (Error bound due to Inconsistent Samples). The error of h can be lower-bounded as
Σ EgE (GED(g g') < 26)
X
Here. the number of inconsistent samples can be approximated via Σ. EgEs.oo'ss (GEED(g.g') < 28) and |x] can be estimated using combinatorial counting procedure. Thus, the above comollary reflects the fact that error inconsistent samples cannot be reduced due to label un-identifiability.
As mentioned before, the generalization bound by HaoChen et al. 15 for SpecLoss is function of a. Deriving a lower bound on a will allow us to comment exactly when error is likely to become vacuous. To this end, need a final definition of partition dissimilarity that induces notion of clustering of similar datapoints in our analysis.
Definition 3.8 (Partition Dissimilarity). Let 5 S, be r-way partition of X. Then, we define the partition dissimilarity for a given partition as
EgEs L(GED(g, g') 28)
xx (S.)
Eges Hg GED'E g') S 25H1
Intuitively, we use the partitions induced by as a proxy for class labels and co-occurrence as a notion of similarity (see Lemma 3.2). Then, the quality of the partition is determined by the ratio
5

---

of the samples that belong to given partition, but are also similar to samples from other partitions, to the total number of samples that are close the partition. Note that partition dissimilarity is an often studied term in clustering problem and a general version of conductance, the property used for spectral clustering on similarity graph which forms the basis of Speclosss [5].
We are now ready to state our main result that re-derives the generalization error of SpecLoss in terms of GGAs, using the definitions of co-occurring pairs (Def. 3.4) and dissimilar partitions (Def. 3.8) Notably, we will decompose bound in terms of the number of co-occurring augmentation-pans the same partition and the number of pairs that cross partitions, which are defined respectively as, A = Eges, .gES. ((GED(g, g') S 26), and μ = Eges. L(GED(g. g') S 26).
within
Theorem 3,9 (Generalization Bound for SpecLoss with GGA). Assume the representation dimension k 2r and Assm. holds for a 2 O. Let F be a hypothesis class containing a minimizer fpop of SpecLoss, L(f), which produces a [k/2]-way partition of X denoted by {S.). Let its most dissimilar partition have dissimilarity denoted by P1R/21 = min; Φ(S; E {S.)). Then, Spop has generalization error bounded as:
{(frop) S (a(a/ = ( 2 (+)
(3)
Discussion. By deriving expressions for and & as well as equivalently representing the original bound in terms of the more intuitive expressions, j and X, we can gain insights into several empirical and intuitive observations in graph CL. We will study these points further in Sec. 4.2 via synthetic dataset that was motivated from the analysis above and allows more fine-grained evaluation.
Invariance and Relevance of Augmentations. GGAs assume that limited changes to a graph's 's struc- ture will not alter its semantics and aggressively increasing augmentation strength will eventually harm generalization. However, through our analysis, we see that the generalization error bound is non-decreasing with respect to ó when X²
и 14, i.e., the number of cross partition pairs dom- inates the expression, as this ratio depends on 6. Indeed, for some 8' = ő + E, where e > J88 Lg ((EE((g g') S 28) + Eges. 11 < GED(g.9') S 28 +))
148 E g' 1(28 < GED(g. g')) s 25 + Thus, the number of cross partitions is always that when augmentations agnostic of the task, their corresponding invariances yield poor representations with vacuous generalization.
non-decreasing with respect to 5. Thus, we clearly
Separability. Our analysis also demonstrates that the success of particular augmentation strength is dependent on the GED between samples belonging to different classes. Given that inter-class GED an intrinsic dataset property that proxies dataset separability, this implies that there are combinations of datasets and augmentation strengths for which GGAs will necessarily incur vacuous bounds, even for low augmentation strengths. In such settings, augmentations that improve recoverability and induce task-relevant invariances are necessary to improve downstream task performance. While many works have conjectured that task-relevant graph augmentations will improve performance, ours is the first to demonstrate why they are needed. Indeed, Sec. 4.1 we find that GGAs are unable to induce such invariances on benchmark datasets.
Recoverability. As shown in Thm. 3.9. better recoverability will improve the tightness of the generalization bound. However, we see that from Coll. B.7 that recoverability will only decrease d increases and as discussed above, there exist datasets where GGAs are not amenable. This further motivates the need for task-relevant augmentations so that the effects of poor augmentations are disentangled from method performance.
Experimental Verification
In this section, we conduct experiments using both standard benchmarks (Sec. 4. and our proposed synthetic dataset generation process (Sec. 4.2) to empirically validate our theoretical conclusions.
4.1 A Closer Look at the Effectiveness of Invariance to GGA
In Sec. we demonstrated GGAs can harm generalization by influencing recoverability and sep- arability. Though computing these properties directly is intractable on benchmark datasets, our analysis for graph datasets and prior works on vision 17 T8 20 show that if augmentations induce invariances that are task-relevant, downstream error should reduce. This corresponds to mcaningfully

---

related samples having similar representations (recoverable) and unrelated samples having dissimilar representations (separable). However. by using augmentations that perturb topology or features constrained to a small fraction of the original graph, existing graph SSL. methods assume such pertur- bations are relevant to the downstream task. If this is the case, our analysis suggests we should see improvement in performance with increased invariance; else, we will witness no tangible correlation.
Experimental Setup: We evaluate seven graph SSL methods on seven, popular benchmark datasets. Specifically, we use the following representative algorithms: (i) GraphCL (22], popular and effective graph CL method; (ii) GAE, Graph Autoencoder - that uses a reconstruction cost to learn representations; (iii)
Autoencoder A5), which we adapt to graphs to create the Augmentation Augmented Graph Autoencoder (AAGAE) that minimizes the reconstruction error between the reconstruction for an augmented sample and the original; (iv) SpecCL, which uses the SpecLoss [5] for contrastive training: (v) SimSiam [2]. a positive-sample-onll framework that uses stop gradient; (vi) BYOL. [21], which avoids negatives samples by using asymmetric branches alongside a stop gradient operation; and (vii) Untrained representations, which have been observed to be surprisingly competitive baselines for graph-based learning 46 47
To the best of our knowledge, ours is the first work to evaluate AAGAE and SpecCL for graph SSL, We use the same augmentations and encoder architecture as GraphCL. We add a straigh--through estimator 4K to GAE/AAGAE's decoder for better training. See Appendix F for further details.
12
GGAs fail to induce task-relevant invariance on standard benchmarks. To measure whether augmentations have induced invariance, we mea- sure recoverability using the representational similarity measures introduced by Wang and Isola 19.. Called Alignment and Uniformity, the two measures are generalized version of the InfoNCE loss and also encompass other contrastive losses, such as SpecLoss. Formally, alignment is defined as: Calign (fi
Method
aagan
byct
goe
grophel
8:61
a.ccurary
spedioss
Dataset
COLLAS
DO
-0.01
IMDS: QAAAT
NUTAC
NCIL
-662
PACTERNS
RECOISERAARY
-8.88
((g-1))~AA1-))) [Ilf(g) f(g')l To deter- mine if the invariance is task-relevant, we determine if improved alignment is indicative of improved performance with respect to an untrained baseline model.
0.15
0.10
0.03 0.00
0.30
Allnvariance
Figure 2: Invariance vs. KNN Acc. The change in- variance (Inv.) and accuracy w.r.t to an untrained model is plotted, where Inv. is measured according to [19]. We see: Inv. has not significantly increased for many datasets/methods,, improved Inv. does necessarily en- tail better performance (see Reddit), and AAGAE/GAE often sees decreased Inv., likely due to use of decoder.
Results. Fig. 2 shows the difference in invariance and KNN with respect to an untrained model's accuracy, averaged over 10 seeds. As can be seen, there is not noticeable correlation between invariance and accuracy, especially with respect to the untrained baseline. Notably, on the Reddit dataset, all methods have improved invariance, but do not have significantly better kNN accuracy. Overall, this experiment demonstrates that learning invariance to GGAs is both difficult and often unrelated to task performance, clearly indicating the GGAs struggle to induce task-relevant invariances and do not support recoverable, separable latent spaces needed for good generalization. Moreover, given that GGAs have unknown recoverability standard datasets, and that trained models not able to sufficiently outperform untrained baselines, there is need for new datasets where is possible to go beyond GGA and where we can better understand the merits of different graph SSL paradigms.
4.2 Evaluating Graph SSL Methods in a Controlled Setting
Our analysis indicates the role played by recoverability and separability under task-relevant invari- ances dramatically influences generalization performance. However, given our results that GGAs do not enable these properties and the fact that task-relevance is difficult to define on existing benchmark datasets, empirical verification of our claims requires a dataset that directly enables control over the data generation process. We thus introduce a synthetic dataset that allows us to illustrate how invariance and class separability must be jointly considered when designing augmentations.
7

---

Style Ratio: 0.5
Style Ratio: 1.0
Style Ratio: 2.0
Style Ratio: 3.0
Figure 3: Synthetic Dataset Generation. A class-specific motif completely determines the label, and is therefore considered "content". To vary the amount of style, the size of the background tree graph is ratio of the number of "content" nodes. Our dataset goes beyond binary benchmarks and allows content- aware augmentations, a critical component to understanding graph SSL.
4.2.1 Synthetic Data Generation Process
Given that standard benchmark datasets and augmentation practices are uninformative when eval- uating the recoverability and invariance of augmentations, propose synthetic data generation process that allows us to understand how the data-dependent assumptions SSL hold for graph datasets. This process not only enables oracle augmentations where recoverability is known, but also allows us some control over dataset separability.
Our synthetic dataset generation process is designed in accordance to a latent variable model which assumes that the underlying data generation latent representation space can partitioned into style and content. Here, style represents information that is irrelevant to the downstream task and can be perturbed (i.e., augmented) without changing sample semantics, while content represents task- relevant information and should be preserved. We note that while von Kügelgen et al. I used the same latent variable model to demonstrate that SSL with data augmentation is able to recover features objective for using this perspective is to develop a grounded
which disentangle style vs. content, benchmark that provides adjustable knobs over content (task-relevant) and style task-irrelevant) information. These knobs allow to understand how data-centric properties affect the performance of different graph SSL algorithms (see Fig. While designing content-aware augmentations for arbitrary graph datasets is hard problem 22 with oracle knowledge of the data generation process, we can evaluate content-aware augmentations (CAAs) with high recoverability at varying levels of separability, which approximate through different style levels.
The proposed data generation process has three components: set C motifs, M, that uniquely determine C' classes; random graph generator, RBG(n), parameterized by the number of nodes (we can equivalently define this based on number of edges); and k, the style multiplier, which controls how much irrelevant information sample contains. To generate sample, we attach a randomly generated background graph (i.e., style component) to a motif (i.e., content) according to the style multiplier. This simple process addresses several limitations often encountered in graph CL. evaluation. Specifically, it (i) allows for varying levels of content-aware augmentation (i.e., edges that can be perturbed in the background graph without harming the motif); (ii) is easily extended beyond binary classification; (iii) contains relatively large number of samples; and (iv)
Generation Process:
offers natural test bed for GNN size generalization or transfer learning
44
4.2.2 Difficulties in Recovering Style Invariant Representations
Several real graph datasets can be understood through a style vs. content perspective. For example, in drug discovery tasks [50]. molecules can be split into functional groups (content) and carbon rings or scaffold structure (style). One may thus ask: how does varying levels of style vs. content affect the performance of graph URL algorithms, and how do different algorithms benefit from the use of content-aware augmentations? To answer these questions, we conduct the following experiment:
and define RBG(n) through a random tree generator, where n is number of the nodes belonging the motif, scaled by к. Node features are constant 10-dimensional vector, To increase task difficulty, we randomly insert between 1-3 motif copies into each sample. Using the specified instaniation of the generation process, we train GraphCL, AAGAE, GAE, and SpecLoss with content-preserving edge dropping and random edge dropping at 20% and 60% augmentation strength. We also evaluate two recently proposed automated augmentation methods, JOAO 29 and AD-GCL as well as SimGRACE 32], which uses implicit, weight space perturbations. JOAO is trained with a GGA prior and an expanded GGA prior that includes
Experimental Setup. Let C 6,
8

---

None
JONO-CMA
JOADHGGM
BIMGRACE
0.9
0.9
0.9
0.9
0.6
0.8
0.8
01.8
Aczureer
Accuracy
0.7
0.7
0.7
0.7
0.9
Grach
SpecLoss
Reconstraciin
Aupomatestmppitt
5 SVC Ratio
8
2
0
2
SvC Ratio
SWC Ratoo
SvC Rado
We evaluate several SSL algorithms with different augmentation paradigms and changing style vs. content ratios. We find several notable results: (i) CAAs induce style invariance in contrastive methods, but GGAs do not; (ii) reconstruction methods do not recover task-relevant invariances, even when using CAAs; and (iii) advanced augmentations methods (AD-GCL, JOAO, SimGRACE) lose performance as style increases, indicating they do not induce style-invariance.
Figure 4: Style Invariance over Paradigms:
content-preserving edge dropping. AD-GCL is trained using a learnable edge-dropping augmentor. A 5-layer GIN encoder is used and models are trained for 60 epochs using Adam (with learning rate of 0.01). After training, all models are evaluated using the linear probe protocol [ at varying style ratios. Given that style information is not relevant the downstream task, we expect models that have truly learned invariance to this information will retain strong performance across different ratios. See Appendix F for more model and training details.
Results. We make the following observations using Fig. 4 which clearly demonstrate the value of the proposed benchmark in studying the behavior of different SSL and augmentation paradigms. (i) In accordance to Sec. 3 we empirically see that both GraphCL and SpecLoss do not loss performance as the style ratio increases when using CAAs, indicating the model has learned task-relevant invariances. (ii) Auto-encoding reconstruction methods are an alternative SSL paradigm, but unfortunately also struggle to recover style-invariant solutions. Moreover, the use of the CAAS with such methods does not improve performance as effectively as in contrastive paradigms. (iii) For the first time, we are able to evaluate whether automated methods, which aim recover strong augmentations without expensive hyper-parameter tuning or hand designing, are able to recover an optimal augmentation that generalizes across style ratios. Unfortunately, we see both AD-GCL Bi and JOAO 2 lose performance as the style ratio increases, indicating such solution has not been found. Indeed, JOAO unable to find such a solution even when the augmentation prior includes the oracle CAAs. These results not only highlight the brittleness of such automated methods, but indicate our benchmark necessary testbed for such methods. (iv) To avoid corrupting graph semantics when using input-space augmentations, SimGRACE 32 instead uses implicit, weight-space augmentations. However, we find, despite tuning the perturbation parameter, SimGRAČE cannot recover strong, style-invariant performance. Overall, using our grounded synthetic benchmark, we are not only able to able to compare the performance of graph SSL algorithms when data-centric properties are supported (e.g., recoverable augmentations), but are also able to identify limitations of advanced augmentation methods that were not apparent using standard benchmarks.
4.2.3 Invariance Separability
CAA
GGA
70.02
We now use our synthetic benchmark to investigate how augmentation recoverability influences the bal- ance of invariance and separability in the learned latent space. Considered in isolation, invariance can be trivially satisfied through representation collapse, i.., all samples are mapped to highly similar repre- sentations. However, such representations are not separable as they cannot meaningfully distinguish classes. Therefore, the following experiment, we jointly consider these properties understand the of CAAs.
10-
49.72
3.714
21.13
Siporsbllt Bay
5.81
0.553
6:51
6,307
6148
0.4
0.5
1.0
Invariance
Figure 5: Invariance vs. Separability. On our syn- thetic data with style-to-content ratio 6 and 20% augmentatin augmentation strength, GraphCI. trained with dom augmentations produces representations with high invariance but low separability. In contrast, us- ing content preserving augmentations leads to almost high invariance, but much greater separability.
Experimental Setup. Using synthetic dataset at 6, we respectively train GraphCI. with content- preserving and random edge dropping at 20% aug-

---

mentation strength. We compute invariance score
for each natural sample by computing the average cosine similarity of its representation with that 30 different augmentations. We compute separability score by dividing the maximum cosine similarity to sample of the same class by the maximum cosine similarity to sample of another class.
Results. Figure 5] shows kernel density estimates of the number of samples that have a given invariance and separability, when training with GGA or CAA. GGA induces representations with somewhat higher invariance but much lower separability scores, suggesting some representation collapse are occurred. Indeed, with higher augmentation strength (60%), we found that using GGA produced invariance and separability scores very close to I for all samples, indicating strong collapse. On the other hand, CAA helps GraphCL achieve over an order of magnitude higher separability and still preserves comparably high invariance. We observed similar trends for SpecLoss.
replicate this experiment using BACE [51], a molecule-protein interaction dataset, and the biochemistry-basee augmentations proposed by Sun al. [52] CAAs. We find that our observations continue hold in this real-world use-case, demonstrating the generality of our theory and practicality of our synthetic benchnmark.
Invariance Separability in Realistic Settings. In App.
Conclusion
In this work, rigorously contextualize, theoretically and empirically, the role of data-dependent properties for graph CL. We propose a novel generalization analysis which, for the first time, formal- izes the limitations of using GGAs in graph CL. As note in Sec. B our results can be extended to other contrastive frameworks by leveraging our insight on representing graph augmentations as composable graph-edit operations and extending the contemporary work of Saunshi et al. AT We suspect similar extension can also be made for predictive methods like BYOL by using the analysis of Wei al. [28 (see App. C.T for further discussion). In line with our theory, we empirically demonstrate that GGAs fail to induce useful task-relevant invariances on standard benchmarks. We note our empirical results already demonstrate the generality of our results across different methods. Moreover, our insights motivate the design of principled synthetic benchmark that provides controlled setting for studying the role of data-dependent properties in graph SSL. Our benchmark also serves as a useful testbed for evaluating the abilities of automated or implicit augmentations techniques. Given the shortcomings we illustrate for such methods on synthetic datasets, we argue the development of domain specific strategies 52 may be a more fruitful direction for future work.
Acknowledgements
This work was performed under the auspices of the U.S. Department of Energy by the Lawrence Livermore National Laboratory under Contract No. DE-AC52-07NA273444 Lawrence Livermore National Security, LLC..and was supported by the L.NNL-LDRD Program under Project No. 21-ERD- 012. PT was intern at Lawrence Livermore National Labs while working on this project. ESL was partly supported via NSF award CNS-2008151.
10

---

References
[1] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In Proc. Int. Conf. on Machine Learning (ICML), 2020.
[2] Xinlei Chen and Kaiming He. Exploring simple siamese representation learning. Proc. Ini. Conf. on Computer Vision and Pattern Recognition (CVPR), 2021.
[3] Jure Zbontar, Li Jing, Ishan Misra, Yann LeCun, and Stéphane Deny. Barlow twins: Self- supervised learning via redundancy reduction. In Pruc. Int. Conf. on Machine Learning (ICML), 2021.
[4] Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross B. Girshick. Momentum contrast for unsupervised visual representation learning. In Proc. Int. Conf. on Computer Vision and Pattern Recognition (CVPR). IEEE, 2020.
[5] Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, and Piotr Bojanowski. Unsuper- vised learning of visual features by contrasting cluster assignments. In Proc. Adv. in Neural Information Processing Systems (NeurIPS), 2020.
[6] Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin. Emerging properties in self-supervised vision transformers. In Proc. Int. Conf. on Computer Vision (ICCV), 2021.
[7] Yonglong Tian, Dilip Krishnan, and Phillip Isola. Contrastive multiview coding, In Proc. Euro. Conf. on Computer Vision (ECCV), 2020.
[8] Aäron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. In Proc. Adv. in Neural Information Processing Systems (NeurIPS), 2018.
[9] R. Devon Hjelm, Alex Fedorov, Samuel Lavoie-Marchildon, Karan Grewal, Philip Bachman, Adam Trischler, and Yoshua Bengio. Learning deep representations by mutual information estimation and maximization. In Proc. Int. Conf. on Learning Representations (ICIR), 2019.
[10] Dan Hendrycks, Mantas Mazeika, Saurav Kadavath, and Dawn Song. Using sulf-supe learning can improve model robustness and uncertainty. In Proc. Adv. in Neural Information Processing Systems (NeurIPS), 2019.
[11] Hong Liu, Jeff Z. HaoChen, Adrien Gaidon, and Tengyu Ma. Self-supervised learning is more robust dataset imbalance. In Proc. Int. Conf. on Learming Representations (ICLR), 2022.
[12] Linus Ericsson, Henry Gouk, and Timothy M. Hospedales. How well do self-supervised models transfer? In Proc. Int. Conf. on Computer Vision and Pattern Recognition (CVPR), 2021.
[13] Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay S. Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. In Proc. Int. Conf. on Learning Representations (ICLR), 2020.
[14] Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, and Nikunj Saunshi. A Theoretical Analysis of Contrastive Unsupervised Representation Learning. In Proc. Int. Conf. on Machine Learning (ICML), 2019.
[15] Jeff Z. HaoChen, Colin Wei, Adrien Gaidon, and Tengyu Ma. Provable guarantees for self- supervised deep learning with spectral contrastive loss. In Proc. Adv. in Neural Information Processing Systems (NeurIPS), 2021.
[16) Yonglong Tian, Chen Sun, Ben Poole, Dilip Krishnan, Cordelia Schmid, and Phillip Isola. What makes for good views for contrastive learnin?? In Proc. Adv. in Neural Information Processing Systems (NeurIPS), 2020.
[17] 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. In Proc. Adv. in Neural Information Processing Systems (NeurIPS), 2021.
11

---

[18] Roland S. Zimmermann, Yash Sharma, Steffen Schneider, Matthias Bethge, and Wieland Brendel. Contrastive learning inverts the data generating process. In Proc. Int. Conf. on Machine Learning (ICML), 2021.
[19] Tongzhou Wang and Phillip Isola. Understanding contrastive representation learning through alignment and uniformity on the hypersphere. In Proc. Int. Conf. on Machine Learning (ICML), 2020.
[20] Senthil Purushwalkam and Abhinav Gupta. Demystifying contrastive self-supervised learning: Invariances, augmentations and dataset biases. In Proc. Adv. in Neural Information Processing Systems (NeurIPS), 2020.
[21] Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre H. Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Ávila Pires, Mohammad Gheshlaghi Azar, Bilal Piot, Koray Kavukeuoglu, Rémi Munos, and Michal Valko. Bootstrap your own latent A new approach to self- supervied learning. In Proc. Adv. in Neural Information Processing Systems (NeurIPS), 2020.
[22] Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. In Proc. Adv. in Neural Information Processing Systems (NeurIPS), 2020.
[23] Kaveh Hassani and Amir Hosein Khas Ahmadi. Contrastive multi-view representation learning on graphs. In Proc. Int. Conf. on Machine Learning (ICML), 2020.
[24] Shantanu Thakoor, Corentin Tallec, Mohammad Gheshlaghi Azar, Medhi Azabou, Eva Dyer, Rémi Munos, Petar Velickovic, and Michal Valko. Large-scale representation learning graphs via bootstrapping. In Proc. Int. Conf. on Learning Representations (ICLR), 2022.
[25] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Graph contrastive learning with adaptive augmentation. Proc. ACM Conf. on World Wide Web (WWW), 2020.
[26] Fan- Yun Sun, Jordan Hoffmann, Vikas Verma, and Jian Tang. Infograph: Unsupervised and semi-supervised graph-level representation learning via mutual information maximization. In Proc. Int. Conf. on Learning Representations (ICLR), 2020.
[27] Yao-Hung Hubert Tsai, Yue Wu, Ruslan Salakhutdinov, and Louis-Philippe Morency. Self- supervised learning from multi-view perspective. In Proc. Int. Conf. on Learning Representa- tions (ICLR), 2021.
[28] Colin Wei, Kendrick Shen, Yining Chen, and Tengyu Ma. Theoretical analysis of self-training with deep networks on unlabeled data. In Proc. Int. Conf. on Learning Representations (ICLR), 2021.
[29] Yuning You, Tianlong Chen, Yang Shen, and Zhangyang Wang. Graph contrastive learning automated. In Proc. Inf. Conf. Machine Learning (ICML), 2021.
[30] 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.
[31] Susheel Suresh, Pan Li, Cong Hao, and Jennifer Neville. Adversarial graph augmentation to improve graph contrastive learning. Proc. Ady. in Neural Information Processing Systems (NeurlPS), 2021.
[32] Jun Xia, Lirong Wu, Jintao Chen, Bozhen Hu, and Stan Z. Li. Simgrace: A simple framework for graph contrastive learning without data augmentation. In Proc. ACM Conf. on World Wide Web (WWW), 2022.
[33] Adrien Bardes, Jean Ponce, and Yann LeCun. Vicreg: Variane-invarracce-cvvrii regular- ization for self-supervised learning. Proc. Int. Conf. on Learning Representations (ICIR), 2021.
12

---

[34] Weiran Huang, Mingyang Yi, and Xuyang Zhao. Towards the Generalization of Contrastive Self Supervised Learning. arXiv, abs/2111.00745, 2021.
[35] Yuandong Tian, Xinlei Chen, and Surya Ganguli. Understanding self-supervised Learning Dynamies without Contrastive Pairs. In Proc. Inf. Conf. on Machine Learning (ICML), 2021.
[36] Li Jing, Pascal Vincent, Yann LeCun, and Yuandong Tian. Understanding dimensional collapse in contrastive self-supervised learning. arXiv preprint arXiv:21100093:3 2021.
[37] Ashwini Pokle, Jinjin Tian, Yuchen Li, and Andrej Risteski. Contrasting the landscape of contrastive and non-contrastive learning, arXiv preprint arXiv:2203. 2022.
[38] Liu Ziyin, Ekdeep Singh Lubana, Masahito Ueda, and Hidenori Tanaka. What shapes the loss landscape of self-supprvvsed learning? arXiv preprint arXiv:2210.006388 2022.
[39] Maria-Florina Balcan, Avrim Blum, and Ke Yang. Co-training and expansion: Towards bridging theory and practice. In Proc. Adv. in Neural Information Processing Systems (NeurIPS), 2004.
[40] Ekdeep Singh Lubana, Chi Ian Tang, Fahim Kawsar, Robert P Dick, and Akhil Mathur. Or- chestra: Unsupervised federated learning via globally consistent clustering. arXiv preprint 1rXi 2022.
[41] Nikunj Saunshi, Jordan Ash, Surbhi Goel, Dipendra Misra, Cyril Zhang, Sanjeev Arora, Sham Kakade, and Akshay Krishnamurthy. Understanding contrastive learning requires incorporating inductive biases. In Proc. Int. Conf. on Machine Learning (ICML), 2022.
[42] Puja Trivedi, Ekdeep Singh Lubana, Yujun Yan, Yaoqing Yang, and Danai Koutra. Augmenta- tions in graph contrastive learning: Current methodological flaws & towards better practices. In Proc. ACM Conf. on World Wide Web (WWW), 2022.
[43] Yeon Chung, Daniel D. Lee, and Haim Sompolinsky. Classification and geometry of general perceptual manifolds. Phys. Rev. X, 8, 2018.
[44] Thomas N. Kipf and Max Welling. Variational graph auto-encoders. In Bayesian Deep Learning Workshop (NeurIPS), 2016.
[45] William Falcon, Ananya Harsh Jha, Teddy Koker, and Kyunghyun Cho. AAVAE: augmentation- augmented variational autoencoders. CORR, 2021.
[46] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. Proc. Int. Conf. on Learning Representations (ICLR), 2017.
[47] Minghao Xu, Hang Wang, Bingbing Ni, Hongyu Guo, and Jian Tang. Self-supervised graph- level representation learning with local and global structure. In Proc. Ins. Conf. on Machine Learning (ICML), 2021.
[48] Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-softmn In Proc. Int. Conf. on Learning Representations (ICLR), 2017.
[49] Gilad Yehudai, Ethan Fetaya, Eli Meirom, Gal Chechik, and Haggai Maron. From local structures to size generalization in graph neural networks. In Proc. Int. Conf. on Machine Learning (ICML), 2021.
[50] Marinka Zitnik, Rok Sosië, and Jure Leskovec. Prioritizing network communities. Nature Communications, 2018.
[51] Govindan Subramanian, Bharath Ramsundar, Vijay Pande, and Rajiah Aldrin Denny Denny. Computational modeling of 3-secretase I (bace-1) 1) inhibitors using ligand based approaches. Journal of Chemical Information and Modeling, 2016.
[52] Mengying Sun, Jing Xing, Huijun Wang. Bin Chen, and Jiayu Zhou. Mocl: Data-driven molecular fingerprint via knowledge-aware contrastive learning from molecular graph. In Proc. ACM Int. Conf. on Knowledge Discovery & Data Mining (SIGKDD), 2021.
13

---

[53]
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
[54] Yanqiao Zhu, Yichen Xu, Qiang Liu, and Shu Wu. An empirical study of graph contrastive learning. In Proc. Neural Information Processing Systems (NeurIPS), Datasets and Benchmarks Track, 2021.
[55] Ben Poole, Sherjil Ozair, Aaron van den Oord, Alexander A. Alemi, and George Tucker. On Variational Bounds of Mutual Information. In Proc. Int. Conf. Machine Learning (ICML), 2019.
[56] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In Proc. Int. Conf. on Learning Representations (ICLR), 2019.
[57] Pinar Yanardag and S. V. N. Vishwanathan. Deep graph kernels. In Proc. ACM Int. Conf. on Knowledge Discovery & Data Mining (SIGKDD), 2015.
[58] Nils M. Kriege and Petra Mutzel. Subgraph matching kernels for attributed graphs. In Proc. Int. Conf. on Machine Learning (ICML), 2012.
[59] 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 Thirleenth International Conference on Intelligent Systems for Molecular Biology, 2005.
[60] Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M. Borgwardt. Weisfeiler-Ihmma graph kernels. Journal of Machine Learning Research (JMLR), 2011.
[61] Nikil Wale and George Karypis. Comparison of descriptor spaces for chemical compound retrieval and classification. In Proc. Int. Conf. on Data Mining (ICDM), 2006.
[62] 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 Proc. ACM Int. Conf. on Knowledge Discovery & Data Mining (SIGKDD), 2020.
[63] Zekarias T. Kefato and Sarunas Girdzijauskas. Self-supervised graph neural networks without explicit negative sampling. In Int. Workshop Self-Supervised Learning for the Web (WW 2021.
[64] Tong Zhao, Yozen Liu, Leonardo Neves, Oliver J. Woodford, Meng Jiang, and Neil Shah. Data augmentation for graph neural networks. In Proc. Association for Advancment of Artificial Intelligence (AAAI), 2020.
[65] 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 Proc. Adv. in Neural Information Processing Systems (NeurIPS), 2019.
[66] Yixin Liu, Shirui Pan, Ming Jin, Chuan Zhou, Feng Xia, and Philip S. Yu. Graph self-supervised learning: A survey. IEEE Trans. on Knowledge and Data Engineering, 2022.
[67] Jiahui Yu, Zhe Lin, Jimei Yang. Xiaohui Shen, Xin Lu, and Thomas S. Huang. Generative image inpainting with contextual attention. In Proc. Int. Conf. on Computer Vision and Pattern Recognition (CVPR), 2018
[68] Yuning You, Tianlong Chen, Zhangyang Wang, and Yang Shen. When does self-supervision help graph convolutional networks? In Proc. Int. Conf. on Machine Learning (ICML), 2020.
[69] Petar Velickovic, William Fedus, William L. Hamilton, Pictro Liò, Yoshua Bengio, and R. Devon Hjelm. Deep graph infomax. In Proc. Int. Conf. on Learning Representations (ICLR), 2019.
14


Reviews:
[{"review_id": "HlYY0jsdMjj", "reviewer": "Reviewer_kxe9", "summary": "This paper investigates how can graph SSL methods work well. Specifically, they first perform a generalization analysis for generic graph data augmentations based on dataset recoverability and separability constraints. Also, they observe that generic graph augmentations adopted in GraphCL do not introduce meaningful invariance. And then, they introduce a designed data generation process to control the amount of content vs. style in samples, which enables to empirically evaluate oracle augmentations. ", "questions": "See the weakness above.", "limitations": "The authors has adequately addressed the limitations and potential negative societal impact of their work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n[+] The paper is well-organized and easy to follow.\n\n[+] The empirical and analytical framework is reasonable.\n\n[+] The codes for reproducing the reported results are provided.\n\n[+] This work shows some insightful opinions on data augmentations in graph contrastive learning. Also, they provide a useful benchmark to better evaluate oracle augmentations.\n\n**Weakness**\n\n[-] Previous works on content-aware augmentations [1] or implicit augmentations [2] in graph contrastive learning should be discussed.\n\n[-] The technical contributions are limited. The content-aware augmentations in this paper only work well in the generated toy dataset.  How can the empirical and analytical framework help us develop more effective graph data augmentations or more powerful graph URL algorithms for practical graph data? \n\n[-] Studying data augmentations in self-supervised learning from a 'content vs. style' perspective has been performed in previous works [3].\n\n[-] I notice that the codes (Readme file) uploaded by the authors include some personal information. If the authors use the open-sourced pyGCL framework, they should cite the paper [4] to violate the anonymity rules. \n\n[1] MoCL: Contrastive Learning on Molecular Graphs with Multi-level Domain Knowledge, KDD 2021.\n\n[2] SimGRACE: A Simple Framework for Graph Contrastive Learning without Data Augmentation, WWW 2022.\n\n[3] Self-Supervised Learning with Data Augmentations Provably Isolates Content from Style, NeurIPS 2021.\n\n[4] An Empirical Study of Graph Contrastive Learning, NeurIPS 2021 (Datasets and Benchmarks track)\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "EfbbEMrYD4e", "reviewer": "Reviewer_1y4x", "summary": "The paper performs systematic and quantitative analyses on the relationship between properties of generic graph augmentations and model performance by deriving the generalization error bound. Analyses and empirical results show that commonly used GGAs do not necessarily lead to task-relevant invariance. Further experimental studies with proposed synthetic data generation indicate benefits from recoverable augmentations.", "questions": "The analysis specifically focuses on the SpecLoss. How would specifically implemented labeling functions and learning objectives (quantitatively) affect the error bound (or can their error bound be derived specifically)? For example, BYOL is different to typical contrastive methods as it does not require negative pairs but experimental studies still include BYOL.", "limitations": "n/a", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\\+ To my knowledge, while adopting existing concepts such as recoverability and separability as a tool, the paper performs the first study to quantitatively study the relationship between measured augmentation properties and the performance (error bound) of SSL methods.\n\n\\+ The proposed theory and its derivation is quite solid. And the empirical results are insightful.\n\n\\- The authors claim that the analysis motivate the necessity of ask-aware augmentations one of their contributions. In fact, the conclusion has been derived from existing studies such as Tian et al. [16] from the mutual information prospect of view, i.e., the worst performance is achieved when there is no task-relevant mutual information overlapping MI of two views. A discussion on the differences and connection of the two groundings could strengthen this as a contribution.\n\n\\- The study mainly focus on the theoretical analysis specifically regarding the GGA in contrastive learning (SpecLoss). The title can be made more specific accordingly to avoid potential over-claim or misleading. Moreover, while strict derivation is not necessary, it'd be better to include discussions regarding how/whether the recoverability and separability can be adopted in predictive methods (or objectives other than SpecLoss) with augmentations (e.g., Section 4.2 of [1*]).\n\n[1*] Xie, Yaochen, et al. \"Self-supervised learning of graph neural networks: A unified review.\" IEEE Transactions on Pattern Analysis and Machine Intelligence (2022).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "8W-e03zXAFx", "reviewer": "Reviewer_SttW", "summary": "This paper theorectically demonstrates why task-relevant graph augmentation is required, using the concept of Graph Edit Distance (GED). In experiments, they showed that existing generic graph augmentation induce limited task-relevent invariance, revealing the error of common graph augmentation practice. To prove their theoretical analysis, they generate synthetic data and show content aware augmentation (task relevant augmentation) improves model performance.", "questions": "- In Assumption 3.3, can the similarity of representation be guaranteed simply with correct classification?\n- Is this theoretical analysis only applicable for SpecLoss?", "limitations": "This work provides theoretical analysis in common practice of graph augmentation. However, it would be better if the authors could validate the practicality of the proposed method, i.e., to real-world graphs.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- This paper has strong theoretical background.\n- Also, to my best knowledge, this work is the first attempt to analyze graph augmentation in terms of Graph Edit Distance (GED).\n- Authors demonstrate their theoretical analysis through experiments on synthetic datasets.\n\nWeakness \n- Paper is hard to read. Specifically, concept of invariance, recoverability and separability should be more clearly defined. Moreover, definition of task relevant augmentation / augmentation that induces invariance to task-irrelevant attributes is not clear.\n- Practicality is limited. Different from image data, it is hard to dichotomously divide style and content in graph domain. I think this is the reason why authors couldn't show the correlation between invariance and accuracy in real-world dataset.\n ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept