Unified Graph Augmentations for Generalized Contrastive Learning on Graphs
Authors: Jiaming Zhuo
Yintong Lu
Hui Ning
Kun Fu
Bingxin Niu
Dongxiao He
Chuan Wang
Yuanfang Guo
Zhen Wang
Xiaochun Cao
Liang Yang
Venue: NeurIPS 2024 poster (2024)
Keywords: Graph Neural Networks
Graph Contrastive Learning
Graph Augmentation
Primary area: graph_neural_networks

Abstract: In real-world scenarios, networks (graphs) and their tasks possess unique characteristics, requiring the development of a versatile graph augmentation (GA) to meet the varied demands of network analysis. Unfortunately, most Graph Contrastive Learning (GCL) frameworks are hampered by the specificity, complexity, and incompleteness of their GA techniques. Firstly, GAs designed for specific scenarios may compromise the universality of models if mishandled. Secondly, the process of identifying and generating optimal augmentations generally involves substantial computational overhead. Thirdly, the effectiveness of the GCL, even the learnable ones, is constrained by the finite selection of GAs available. To overcome the above limitations, this paper introduces a novel unified GA module dubbed UGA after reinterpreting the mechanism of GAs in GCLs from a message-passing perspective. Theoretically, this module is capable of unifying any explicit GAs, including node, edge, attribute, and subgraph augmentations. Based on the proposed UGA, a novel generalized GCL framework dubbed Graph cOntrastive UnifieD Augmentations (GOUDA) is proposed. It seamlessly integrates widely adopted contrastive losses and an introduced independence loss to fulfill the common requirements of consistency and diversity of augmentation across diverse scenarios. Evaluations across various datasets and tasks demonstrate the generality and efficiency of the proposed GOUDA over existing state-of-the-art GCLs.

Unified Graph Augmentations for Generalized Contrastive Learning on Graphs
Jiaming Zhuo', Yintong Lu', Hui Ning', Kun Fu', Bingxin Niu Dongxiao He?, Chuan Wang", Yuanfang Guo?, Zhen Wang?, Xiaochun Cao Liang Yang!*
Hebei Province Key Laboratory of Big Data Calculation, School of Artificial Intelligence, Hebei University of Technology, Tianjin, China "College of Intelligence and Computing, Tianjin University, Tianjin, China Schooo of Computer Science and Technology, Beijing JiaoTTong University, Beijing, China
School of Computer Science and Engineering, Beihang University, Beijing, China Schooo of Artificial Intelligence, OPtics and ElectroNics (iOPEN), School of Cybersecurity, Northwestern Polytechnical University, Xi'an, China
School of Cyber Science and Technology,
Shenzhen Campus of Sun Yat-sen University, Shenzhen, China
j jamingg zhuo@outlook, com, 202332803037 hebut. edu..duuuooooooooo en, ninghui 0480168800 63. com, fukunShebut.c edu cn, niubingxin6666168. com, deedongxiaotjjie edu. cn, wangchuan@iie.cc ac. en, andyguo@buaa edu. cn, w-zhen@nwpu.c edu. cn, caoxiaochunOmail. sysu. edu. cn, yangliangévip.com com
Abstract
In real-world scenarios, networks (graphs) and their tasks possess unique character- istics, requiring the development of versatile graph augmentation (GA) to meet the varied demands of network analysis. Unfortunately. most Graph Contrastive hampered by the specificity, complexity, and in-
Learning (GCL) frameworks completeness their GA techniques. Firstly, GAs designed for specific scenarios may compromise the universality of models if mishandled. Secondly, the process of identifying and generating optimal augmentations generally involves substantial computational overhead. Thirdly, the effectiveness of the GCL, the learnable ones, is constrained by the finite selection of GAs available. To overcome the above limitations, this paper introduces novel unified GA module dubbed UGA after reinterpreting the mechanism of GAs in GCLs from a messagc-passing perspective. Theoretically, this module is capable of unifying any explicit GAs, including node, edge, attribute, and subgraph augmentations. Based on the proposed UGA, novel generalized GCL framework dubbed Graph cOntrastive UnifieD Augmentations (GOUDA) is proposed. It seamlessly integrates widely adopted contrastive losses and an introduced independence loss to fulfill the common requirements consis- tency and diversity of augmentation across diverse scenarios. Evaluations across various datasets and tasks demonstrate the generality and efficiency of the proposed GCLs.
GOUDA over existing
Introduction
Owing to their effectiveness and efficiency, Graph Neural Networks (GNNs) have become standard toolkit for processing various graph tasks such as node classification and graph classification [17] 34]
41 40). They typically follow message-passinnn paradigm [10), where the representation of each node updated by aggregating the representations of its adjacent nodes and subsequently combining
corresponding author
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

the aggregated representations with itself. In general, to produce discriminative representations, GNNs need resort to the task-relevant labels (i.e., supervised information) to guide the network training. which limits their applicability in the label scarcity scenarios [24 37 43 To overcome this limitation, Graph Contrastive learning (GCL), a typical graph self-supeviiee learning architecture, has been developed to provide training guidance by capturing the self-supervised information contained in the
graph [53 32 50 2
21 39 20).
Inspired by the design philosophy of contrastive learning in Computer Vision (CV) 4 GCLs adopt the same architecture, which consists of three components: augmentation, encoder, and con- trastive loss [53] 32). Thus, GCLs inherit the merit of enabling learning representations invariant to augmentation, which is achieved by maximizing the agreement between embeddings from different perturbations of the same graph [31 [5]. To further improve the representation capacity of GCLs, great endeavors have been made to design augmentations for the original graph, i.e, Graph Augmen- tations (GAs), which target nodes, edges, attributes, and subgraphs. Based on how information is processed, GAs can be divided into two categories: heuristic [53 35 32
14] and learnable methods 47 21 The heuristic GAs modify graphs through the combination of fixed, random rules, such as attribute masking [53], edge removing [32, 2), and graph diffusion [1]. They tend to neglect the subsequent steps, namely encoding and contrastive optimization, hence leading to suboptimal performances. In contrast, learnable GAs leverage prior knowledge and feedback during training to refine augmentations, already surpassing base augmentations many tasks. Notable contributions include GAs based on spectral methods [2I). and adversarial training [1I]
Given their inherent and distinct characteristics, various networks and tasks require the meticulous selection of optimal GAs to improve model performance pivotally. However, most GCLs face several limitations regarding the selection: (1) Specificity. GCLs are typically tailored with specific GAs to meet the needs of particular scenarios, resulting in a lack of generality across diverse scenarios. For instance, node dropping (specifically, removing nodes and their associated edges), widely applied in graph-level tasks [47 48), could significantly compromise the integrity of graphs (36), rendering less suitable for love- tasks. (2) High complexity. Either way, identifying and generating the spene-specific GAs impose a considerable computational burden on the models. For example, the set sampling method necessitates a validation of all combinations [45] (38. Furthermore, the adversarial attack method [I] entails recalculating contrastive losses, which takes a quadratic complexity of On?²). Besides, the spectral method requires Laplacian matrix decomposition (5), which has cubic complexity of O (3) Incompleteness. Despite the promise of existing learnable GAs in optimizing for specific scenarios, their efficacy is limited by the finite range of GAs at their disposal.
This paper seeks to break these limitations by proposing a unified GA module for GCLs. Toward this end, the mechanisms of existing GAs in GCLs are systemically investigated and reinterpreted from a message- passsegganinggggg perspective [TO]. The conclusion is that, from the message-passing perspective, GAs uniformly induce attribute modifications within the neighborhoods of nodes, even though they appear diverse from the spatial perspective, as depicted in Fig. [ Therefore, the essence of GCLs is to learn node representations invariant to such local augmentation. Drawing from this insight, a novel Unified GA (UGA) module with a simple yet effective design is presented. It strategically interpolates (AC) vectors in graph-structured manner (55] R)
an appropriate amount of Augmentation--emnt where AC vectors are treated as another type of node, as illustrated in Fig. [ In theory, UGA is able to simulate the impact of the above four explicit GAs on target nodes by aggregating features from the AC vectors that capture the attribute variations within the neighborhood of these nodes.
Building upon the proposed UGA module, a generalized GCL framework dubbed Graph cOntrastive UnifieD Augmentations (GOUDA) is presented to overcome the above challenges in existing GCLs. This framework adopts typical dual-channel architecture 4 49 (53, corresponding to two distinct augmented graphs (views) with their respective AC matrices, as shown in Fig. 2 To realize general utility, GOUDA proposes capture the consistency and diversity across augmentations (defined in Section 3.3). which are essential and shared goals for GCLs to be applicable across diverse scenarios. To be specific, the objective function of GOUDA is twofold: (1) maximizing Mutual Information (MI) between representations from these distinct views. (2) maximizing the distributional difference between the AC matrices. The former is a fundamental principle behind classic contrastive losses and inherently ensures consistency, while the latter is a constraint to modulate diversity. In practice, GOUDA is instantiated by leveraging widely employed contrastive losses alongside -cchidt Independence Criterion (ESIC)-basee distributional independence loss. This design makes GOUDA more effective and efficient than GCLs with learnable GAs.
2

---

The main contributions of this work are summarized as follows:
We investigate the mechanism of GAs in GCLs through the lens of message- paassag-passing.
We propose a lightweight GA module named UGA to simulate the impacts of GAs on nodes.
We introduce GOUDA, an efficient and generalized GCL framework, which captures both consistency and diversity actoss augmentations.
Extensive experiments and in-depth analysis demonstrate that GOUDA outperforms state- of-the-art GCLs across various public benchmark datasets and tasks.
2
Preliminaries
This section briefly introduces the notations utilized throughout the paper. Subsequently, outlines the essential components of the Graph Contrastive Learning (GCL) framework.
2.1 Notations
Matrices (e.g., Q) are in bold capital letters, vectors (e.g., qi.: which denotes the i-th row of Q) are in bold lowercase letters, scalars (e-g-, Pi.j which represents the entry of the i-th and the j-th column) are in lowercase letters, and sets () are in calligraphic letters.
For a general-purpose description, this paper considers an undirected attribute graph G(V,E), E), where V stands for the node-set containing node instances {(x.. ye)h And X E RR"xf and Y E R"xe denote the attribute matrix and label matrix of node v. respectively, where / and e is the numbers containing m edges.
of attirbutes and labels, respectively. Also, & fe, )m-1 terms the edge sraphoopoloyy In general, the adjacency matrix A E R=x= is employed to describe the graph topology. such that the matrix form of the graph can be expressed as G(A, X). Moreover, H 12axd terms the graph representation, where d terms the dimension of the representation.
2.2 Graph Contrastive Learning
Drawing on the successful experience image augmentation Computer Vision (CV) [5). Graph Augmentation (GA) [51] is introduced in graph learning to address the chal- lenge data scarcity. In the typical GCL frameworks, the input graph ( X) is processed through two separate perturbations (GA procedures), formulated as (g( )))+ : G(A, X) + (A (0) (()) to generate its two views (augmented graphs), denoted as 91 (A ( and (2 (2), x(2). Based on the perturbed information, GAs be broadly classified into four main categories: node aug-
Graph Augmentations.
mentation [47 48), edge augmentation [53] 54 32 B1, attribute augmentation 19 53 and
subgraph augmentation 47 13)
An overview of GAs can be found in Section B
Graph Encoders. For efficient processing and analysis, the graph encoders are leveraged to transform raw topology and attribute information of the input graph into low- dimensional vector representations. Most graph encoders in GCLs follow a message-passing paradigm [10, which typically involves two primary processes: aggregation and combination. During these steps, each node iteratively updates its representations by aggregating and combining the node features from its neighborhoods, that is
h A Aggregation' / (fh EN.) h. A Combination' ' (h!-1, i...
(1)
where hy, terms the representations of node in the 1-th layer and N₁, denotes the set of neighboring nodes of node e. In prevalent GCLs like GRACE [53] two-layer GCN [17 is adopted, where the Aggregation( (.) and Combination()) functions are implemented via average function. Thus, there is
H GCN2 (A, (A) = (D- AD ( AD - +xw") w').
(2)
where a--) denotes the nonlinear activation functions, such as ReLU(-)). and A A + I, stands for the adjacentcy matrix with self-loops, and ò the corresponding degree matrix, and W represents the parameter matrix for the 1-th layer. Therefore, for the two augmented graphs, their representations can be obtained by computing (1) GCN² (1), x (1)) and (2) GCN² (G (2), ( x (2)).
3

---

Spatial Perspective
GA
Imput graph G(A, Exampler layaayerrr GUN
Augmented graph (17))
Augmenntd gragh C
Augmensed graph G, (A.
Augmeented gruph C (x
1 1-pp
1-ep
hop...
24hep
2 hoop
2-hop wibgraph
Message-passingg Perspective
(a) Node Augmentation.
(b) Edge Augmentation.
(c) Attribute Augmentation.
(d) Subgraph Augmentation.
Figure I: Motivation to unify Graph Augmentations (GAs). A two-hop subgraph example, where the target node is highlighted in red, and the perturbed information is marked in brown. (a) Node augmen- tation by dropping nodes. (b) Edge augmentation by removing edges. (c) Attribute augmentation by masking attributes. (d) Subgraph augmentation by cropping subgraphs. Existing GAs, typically seen as various forms of global augmentations from the spatial perspective, can uniformly interpreted as local attribute modifications (i.e., local augmentations) from the message-passiien perspective.
Contrastive losses. In line with the InfoMax principle [22]. various contrastive losses are incorporated in GCLs, guiding the training graph encoders by maximizing the Mutual Information (MI) between the encoded representations and (2) obtained from shared encoder 8e. the general objective of GCL is expressed as
augmented graphs. Specifically, given two representations H
GCL:
arg max ((H H()),, where H (e H2) = (9()),
where [(X; Y) represents the MI between and Y. In general, the MI can be approximated using a lower bound estimator, i.e., the InfoNCE loss (33], in the GCLs [53] 20). This loss be classified as a sample-level loss because operates on the sample dimension of the representation matrix. In contrast, Barlow Twins loss [49], another widely employed loss, is designed
remove redundancies among features and hence can be categorized as feature-level loss. Both losses are used to implement the proposed framework. Section C provides detailed descriptions of these losses.
Methodology
3.1 Motivations
As previously mentioned, Contrastive Learning (CL) seeks to learn image representations invariant to augmentations by encouraging the agreement between embedding vectors from the different image distortions. Due to the employment of identical loss functions, typical Graph Contrastive Learning (GCL) inherits the above representation capabilities from CL. Nonetheless, GCLs should emphasize the local invariance owing to the application of graph encoders.
The essence of the graph encoder is to explore the locality of graphs. To be specific, graph encoders in GCLs (generally a 2-layer GCN) follow the geessageppsssnng paradigm where node representations are updated in local aggregation and combination manner, as detailed in Section 2 Given the localizing property of the graph encoder, GAs (i.e., node, edge, attribute, and subgraph augmentations), which typically viewed as global operations in various forms, can be uniformly reinterpreted as attribute modifications in the neighborhoods of nodes, namely, local augmentations, as illustrated in Fig. !
1) Edge augmentation involves adding and removing perturbed edges in graphs, equivalent to inserting or masking the attributes of nodes connected by these edges in the neighborhood of impacted nodes. For example, the shown edge removing results in the complete attribute masking of partial 2-hop neighbors (nodes 1, 4, 7, and 8) the target node during message passing. 2) Attribute augmentation essentially replaces the attributes of perturbed nodes in the graph with new ones, which can be viewed as perturbing the neighborhoods of nodes that contain these perturbed nodes. The attribute masking example shows that during the aggregation phase, the attributes of neighbors (nodes 1, 3, 4, 5, 6, 7,

---

and 8) on the 2-hop computation graphs of node O are masked. 3) Subgraph augmentation is to modify the specific subsets of the graph (including its edges and attributes), which also can be seen as the attribute perturbation in the neighborhoods of target nodes. For node 0, the shown subgraph cropping causes removing nodes 2, 4, 6, and 8 from the 2-hop neighborhood during the caasaag--passing phase. Note that node augmentation is a specific case of subgraph augmentation, where the subset size is one. Thus, the above conclusion regarding subgraph augmentation applies to it.
In short, the mechanism of GAs in GCLs is to induce attribute modification in the neighborhoods of nodes. Thus, the essence of GCLs is learn representations invariant to such local augmentations.
3.2 Unified Graph Augmentation Module
Motivated by the above insights, a unified graph augmentation module dubbed UGA is introduced to implement augmentation efficiently and flexibly. The primary idea is to introduce collection of Augmentation-
(AC) vectors for nodes to simulate and exert the impact of GAs on these nodes, namely, attribute variations in the neighborhood of these nodes. A straightforward implementation of UGA is to align AC vectors one-to-one with nodes, match the size of their features, and then perform feature summation achieve the desired augmentation.
Given the input graph G. the above implementation can be formulated as
UGA: G- t(g, Q), where t(G, Q) G(A,X) - G(A,X+ Q),
(4)
where G. denotes an augmented graph derived from the UGA funtion t(G Q). and Q E R2xx terms the matrix of AC vectors q, R xx i.e., AC matrix, and is the dimension of node attributes.
Fig. 2]a) provides an illustrative example and explains the equivalence between the proposed UGA module and explicit GA (edge removing). From this, it can be concluded that the UGA module can effectively substitute GAs as long as the combined AC vectors are the representations of cumulative attribute variations within the neighborhoods of nodes induced by these GAs.
Theorem 3.1. Assuming any augmented graph G- (A(A (+), x()),, where (+) A and X(+) with A and X represent the candidate spaces for the augmented adjacency matrix and attribute matrix, respectively, in the proposed implementation of UGA (Eq. there exists an AC matrix Q that meets
ge EA Q) ge A x()).
(5)
where ge stands for the graph encoder.
This theorem suggests that the proposed UGA module can be equivalent to any existing GA (including node, edge, attribute, and subgraph operations), thereby demonstrating its unifying capability to GAs. Proofs for this theorem are presented in Section D.I. Furthermore, the UGA module possesses an attractive characteristic: adaptability, since the AC vectors are capable of dynamically capturing task- relevant perturbation information throughout the training process. Nonetheless, this implementation introduces numerous parameters proportional to the network size, resulting in significant increase in complexity and the risk of overfitting. To address this limitation, the proposed UGA is reimplemented in graph-structure manner, where a modest parameter set is utilized, as shown in Fig. b).
Shared AC vectors. In graphs, long-range dependencies sigmify the beyond-loca interactions among nodes, represented by similar node attributes and neighborhood patterns [23] 40 46. Therefore, is reasonable to assume that group of interdependent nodes would benefit from the same optimal GAs. Thus, a shared AC matrix Q [q:: 1-1 is introduced, where k < n.
Propagation mode. AC vectors propagate their features to nodes via a general attention mechanism, in which structural features (e.g., positional/structure encodings (17) are employed to calculate the attention scores. Formally, the proposed UGA module can be reformulated as
exp (I([x..) (eo..))
* X
Σ 1=0
qr.:
b
Σn exp (f([x.,. (/e...,//eev.))) qT.)"
where by.s stands for the propagation weight from i-th AC vector to node within matrix B E B and f([xx.Iee.) E RIX terms an integrated representation of node v, which concatenates the node attributes x, and structural features e, E R'. This paper adopts 1-steps random-wall walk encodings as the structure features. f(-) /+2 + R denotes projection layer.
5

---

Graph Encoders
Embeddings
Augmented graph (A.
G2 T(G, (
Equivalent
Independence Loss
Shared ga(.)
Contrastive Loss
G2 (G.
Inpat graph ((A.))
Eanholdings
1-hop
Gruph Einooders
whire 3
proposed GA module UGA.
(b) The proposed GCL framework GOUDA.
Figure 2: Illustration of the proposed unified module UGA and generalized framework GOUDA. (a) An intuitive example of the equivalence between GAs (e.g., edge removing) and the aggregation of Eeamentation-Centree (AC) vectors, which capture the local attribute variations caused by these GAs. (b) The proposed generalized GCL. framework GOUDA. The independence loss, which is directly computed AC vectors, is designed ensure diversity across different augmentations.
Processing. Keeping a subset the salient connections facilitates propagation and enhances compu- tational efficiency. Thus, propagation weights below predefined threshold are zeroed out, namely
(u,s: b >
b
0, otherwise,
where terms a threshold value. Then, the obtained weight B is applied in propagation, per Eq
3.3 Generalized Graph Contrastive Learning Framework
Building upon the UGA module, a novel GCL framework named Graph cOntrastive UnifieD Aug- mentations (GOUDA) is proposed achieve generality across diverse tasks and graphs. It utilizes the standard two-channel architecture (in Eq. B}. with each channel generating an augmented graph through the UGA module and AC matrix, as depicted in Fig. Unlike traditional GCLs, GOUDA introduces term to constrain the two AC matrices (denoted as Q and P).
Specifically, GOUDA optimizes the following objective function:
GOUDA: argmax (ge (G1) ) ge (G2)) + D (Q.P),
(8)
where 1(X; Y) stands for the Mutual Information (MI) between X and Y, and Be denotes graph encoder shared between two views (or channels). 9 = t (G, Q) and G2 = t (g, P) represent two augmented graphs, and D (Q, P) denotes the constraint between Q and P.
Definition 3.2. (Consistency across augmentations)). Let (t) and H denote the representations of graphs Gú, 9j G., respectively, where j o i, and G. denotes the family of graphs derived from series of parametric graph augmentations. Consistency across augmentations for node u is defined as
C, S h
where S(X, Y) terms the distributional similarity between X and Y.
This consistency implies that augmentation should minimally impact the similarity between repre- sentations from different augmented graphs for the same nodes to preserve the intrinsic semantic integrity of the nodes. Note that the first term in the objective function of GOUDA, namely the MI maximization, essentially is a constraint for semantic consistency. Thus, the augmentation learned by the UGA module capable of ensuring the desired property.
Definition 3.3. (Diversity across augmentations). Given two augmented graphs (A(A ()) and (A(), X6) ~ Gu. where A let V represents the k-hop subgraph centered at node v, and let D(,) stands for the measure of distributional difference. Diversity across augmentations is defined as
D. = D (COM(X (6) ) COM((X)) (2))
(10)

---

where X Ny E ERX.X stands for the attribute matrix of nodes in the k-hop subgraph of node and Ty is the number of neighbors for node v. COM(-) terms a combination function, such as sum
This definition is based on the conclusion in Section 3.1 namely, the mechanism of GAs in GCLs is to modify attributes within the node neighborhoods. Accordingly, another objective for augmentation the minimization of the local attribute overlap between augmented graphs, ensuring the model does not overfocus the specific features of single distribution.
In the proposed GOUDA framework, local attribute variations for each node are represented by AC vectors, e.g., q. and Po. with the augmentation being generated by aggregating features from these vectors. Therefore, the diversity across augmentations can be quantified using two AC matrices (Q and P) corresponding to two distinct views, which is supported by the following analysis.
Theorem 3.4. Let D(X, Y) -|
stands for the distributional difference, and let COM(-) sum terms the combination function. In GOUDA (in Eq. 8 the diversity across augmentations (in Eq. can be upproximated by the distributional difference between AC matrices Q and P, that is
YI
D = Σ
(x
+ (..))
Σ
(x
+p..))
Ri 1Q P
(11)
BENGUe
LEN
where qr. = by Q denote the features propagated from AC matrices Q to node t.
Theorem shows that the diversity across augmentations can be controlled by imposing constraints on the AC matrices, particularly through the second term in the objective function of GOUDA. Refer to Section for the proofs. In brief, maintaining a balance between consistency and diversity across augmentations is crucial for the effectiveness of GCLs. Specifically, diversity encourages exploring and exploiting the local attribute variations while consistency anchors the learned representations to the original semanties.
3.4 Instantiation of GOUDA
This subsection introduces a practical implementation of the proposed GOUDA framework (Eq The overview of this framework is depicted in Fig. 2 while the step-by-step procedure is detailed in Algorithm|] [ The objective of GOUDA is to learn the discriminative and robust representations. To achieve this, it seeks to train the graph encoder ge to maximize the Mutual Information (MI) between representations from two augmented graphs 91 t(G Q) and G2 tG) while simultaneously maintaining consistency and diversity in the augmentation process.
Estimation of Mutual Information (MT). The first term of GOUDA is implemented utilizing the sample-level InfoNCE loss (in Eq. 22). which serves as a lower bound estimator for MI, and the feature-level Barlow Twins loss (in Eq. 24p. This term is denoted as contrastive loss Ccontrast Owing to limited space, the above losses are introduced in Section C
Distributional independence loss. A distributional independence loss is introduced to instantiate the second term of GOUDA. Specifically, the Bilbert-Schmin Independence Criterion (HSIC) [ is adopted measure the statistical dependence between two augmentation distributions. Furthermore, the Gram matrices derived from HSIC are constrained to minimize their off-diagonal elements. To be concrete, the independence loss is formulated as
Lindep 1/(n 1)2 trace (KRLR)) 31 ΣΣ k:s + B2 EE5EE,. J+1
(12)
HSIC
J+
where K and L stand for the Gram matrices of Q and P. respectively, defined by k.j ( qaa) and 4., = x <(P... ). In practice, the kernel function x(-) is defined as the linear kernel, specifically kig = .h. Additionally, R = I, _11 represents the centering matrix, where I E R and 1, E 1 denote the identity matrix and all-one column vector, respectively. 81 and 13 represent two hyper-parameters. Minimizing this term serves two purposes: on the one hand, it enhances the diversity across augmentations by amplifying the differences between two distributions, and on the other hand, avoids trivial solutions by increasing the differences among the augmentation elements (g..) within each distribution.
Objective. The overall objective function of GOUDA is weighted sum of these two terms, that Levatrast + Lindeps
(13)
where y denotes a hyperparameter used trade off two terms.
7

---

Table Comparison of time complexity in the augmentation Phase. n denotes the size of the graph.
Model
Time Complexity
Description
SPAN
21
t(n
Rigendecompossition-eeee based edge augmentation.
JOAO 47
((n-d)
Min-max optimization based augmentation.
AD-GCL 31
O(n"d)
Adversarial--raining-- bhasn edge augmentation.
GOUDA (Ours)
((nkf)
Consistency-diverrse balanced augmentation.
Table 2: Accuracy in percentage (mean over ten trials of node classification across seven graphs. Best and runner-up models are highlighted in bolded and underlined, respectively.
Model
Input
Cora
CiteSeer
PubMed
Wiki-CS
Photo
Computers
Physics
GCN
A.
12.32+1.79 72.13
84.90
76.89+0.3
02.35+0.25
86.3420.46
95.65 06.65
GAT
A, X.
83.34
22.44
85.21
77.42+0.1 19
92. 92.3540.25
87 87.0620.35
95.47
DGI
A,
82.6010.40
71.4910.14
75.7310.15 86.0010.14
84.0910.30 11.49
94.51 10.52
GMI
A, X
11.47
11.56
75.0610.13 14.80
90.7210.33
81.7610.55
94.1010.61
MVGRL
X
83.0310.27
72.75.0.40
77 17.97 15.63
92.0110.13
87 17.0011.20
95.33 10.03
GRACE
X.X
83.30:0.40
71.41
86.5140.34
79.1640.30 s6
92.63-40.32
87. 37.21:::44
95.26
GCA
A, X
83.90 83.90.0.41
72.21
79.35.10.1 86.01
92. 17
87 37.84:00.0
95. (55.68.. 10.05
BGRL
X 80.77
71.99=0.42
84.9440.17
78.74 78.7440.22
93. 03.2440:29
88 58.92=0038
95, 43.03
GBT
X
83, 43.89
72.57
85.71
76.65-0.62
92. 02.6340.44
88. 14:4..3
95,07
CCA-SSG
A, X
84.39
73.81 =0.38
86.21
78.94
93. 1440.14
88. 28.74
95.38
SPAN
A, X
85. 85.09
73. 20.5
85.35 85.35
79.01
92. 02.6840.31
89 68.
95, 12
DSSL
A,
84.52
73.93
73.93
85.59
79.98
93.0840.38
29.06..0.9
95. 40.29
HomoGCL
A,
84.8910.71
13.78
16.37
79.2910.32
92.9210.18
88.46
95. 18.09
GOUDA-IF
A. X
86. 10.11-00 10.55
74.55
87.55 10.10
80.61
93.69 10.32
89.21
96.09 10.14
GOUDA-BT
A, X
85.99 40.31
74.47
87.5920.02
80.37 30
93. 93.8222011
89.55
96.1920.21
3.5 Complexity Analysis
This subsection evaluates the complexity of the proposed GOUDA framework in comparison to the baseline GCLs configured with learnable GAs, including SPAN, JOAO, and AD-GCL. As illustrated in Tab. GOUDA introduces lighter computational overhead compared to these baselines. For a detailed description of the complexity, refer to Section E.4
Experiments
This section evaluates the effectiveness and generality of the proposed GOUDA through a compre- hensive comparison against multiple baselines across tasks at both the node-level (node classification and node clustering) and the graph-level (graph classification) tasks. Furthermore, it conducts several additional experiments to deepen the understanding of this framework. For exhaustive account of datasets, baselines, configurations, and hyper- setetrrrraaaereeeeee refer to Section E
Datasets. The experiment utilizes ten benchmark datasets, namely: Cora 28 CiteSeer (28 PubMed
28 Wiki-CS (25), Photo (29), Computers (2)), and Physics [29] for node-level tasks, and IMDB-B
42
IMDB-M 42 and COLLAB [2] for graph-level tasks. See Section E.1 for dataset descriptions.
Baselines. The baseline models comprise two supervised graph neural networks (GCN [17] GAT
34)) and eleven self-supervised graph learning models (DGI (35), GMI [26), MVGRL 14] GR GRACE
[33. GCA [54], BGRL [32], CCA-SSG (50). GBT (2) SPAN (2T). DSSL 39 HomoGCL 20) for
node-level tasks, Four self supervuee learning models are compared (InfoGraph [30], GraphCL
48
JOAO 47) AD-GCL (3I) for graeh-level tasks, Refer Section E3 for model introductions.
4.1 Experimental Results
Node Classification. can be observed from Tab. 2 which exhibits the results of node classifica- tion tasks, that the proposed GOUDA outperforms the unsupervised baselines in six of the seven datasets. This demonstrates the superiority of GOUDA. Furthermore, on the CiteSeer dataset, notable performance improvements are observed with both models, GOUDA-IF and GOUDA-BI -T, surpassing

---

the baselines GRACE and GBT. Specifically, the accuracy of GOUDA-IF surpasses that of GRACE by 3.14%, and similarly, the accuracy of GOUDA-BT exceeds that of GBT by 1.90%. Note that the baselines GRACE and GBT adopt identical encoders and contrastive losses as GOUDA-IF and GOUDA-BT, respectively. Therefore, the observed performance improvement can be attributed to the adaptive modeling capacity for augmentations of the proposed GOUDA.
Node Clustering. One can draw two conclusions Table 3: Performances node clustering: NMI
from the observations in Tab. 3 Firstly, it is evi- & ARI Scores in percentage (mean).
dent that GOUDA consistently surpasses all base- lines (e.g.. GRACE, and GBT) across all datasets, which illustrates the superior representation capac- ity of GOUDA. This can be attributed to the self- adaptive learning ability of the proposed module "GGA.Seconde GOUDA-IF consistently outper- forms GOUDA-BT, suggesting that within the pro- posed GOUDA framework, the InfoNCE loss more effectively captures local information for cluster- ing than the MarlowTwins loss.
Cora
CiteSeer
PubMed
NMI
ARI
NMI
ARI
NM1
ARI
DGI
52.75
47.78
40.43
41.84
30.03
29.78
MVGRL
54.21
49.04
43.26
42.73
30.75
30.42
GRACE
54.59
48.31
43.02
42.32
31.11
30.37
GBT
55.32
48.91
44.01
42.61
31.33
30.64
CCA-SSG
56.38
50.62
43.98
42.79
32.06
31.15
GOUDA-IF
57.92
52 41
45.11
11
43.82
33
17 31.98
GOUDA-BT
57.35
51.84
44.93
43.46
33.14
31.73
Graph Classification. The results of this experiment are presented in Tab. 4 and Fig. Firstly, it can be observed from Tab. that GOUDA outperforms the baselines regarding classification performance, which illustrates the general validity of GOUDA. In particular, GOUDA-IF and GOUDA-BT surpass the second-place MVGRL by 1.02% and 2.6%. respectively, on the IMDB-B B-B dataset, which highlights the superiority of GOUDA. Moreover, GOUDA exceeds the GCLs employing leamable GAs, ie.. JOAO, and AD-GCI. This can be due to the unified ability of UGA to integrate diverse GAs, which provides GOUDA with broader augmentation options than the baseline. Secondly, illustrated in Fig. 3 GOUDA achieves superior performance and consumes less time than the baselines. Specifically, two triangles, indicating the proposed GOUDA, are superior left and above the other shape in the figure. This implies GOUDA is lightweight, aligning with conclusions in Section 3.5 Besides, UGA introduces modest memory usage, which promises the scalability of GOUDA.
Acc. Time Memory
Acc. Time vs. Memory
Table 4: Performances on graph classification:
accuracy in percentage (mda
Accuracy()))
76
Manh
Kiks
Model
IMDB-B
IMDB-M
COLLAB
8
cornommen
Infograph
73.0310.87
82.00 19.69
GraphCL
71.1410.44 18.68
71.36
JOAO
71.60+0.66
70.40 49.20+0.17
0.5
Timeiepoc((s)
1.0
1.5
0.5
Time' (pmeeeppchis) (b) IMDB-M
1.0
1.5
AD-GCL
71.49+0.30
50.3640.74
74.80
(a) IMDB-B
MVGRL
74.20
51.20
73.10.0..0
Figure 3: Comparisons in terms of performance, running time, and GPU memory usage. The marker size indicates memory usage.
GOUDA-IF
75.22
52.43
10.63
85. 35.70
GOUDA-BT BT
76.80
53. 20.05
85.15.2.11
4.2 Additional Experiments
Robustness Analysis. This experiment aims to evaluate the robustness of GOUDA against topology attacks (adding edges) and attribute attacks (flipping attributes). According to results in Fig. Fand Fig. 5] several conclusions can be derived. Firstly, compared to the baselines using the same contrastive losses, GOUDA consistently achieves performance gains at all perturbation rates. It demonstrates the robustness of GOUDA against both topology and attribute attacks. This is attributed to the greater adaptability of the UGA module, stemming from its integration of augmentation and contrastive updating over random GAs. Secondly, attribute attacks cause more severe performance degradation than topology attacks, even for our proposed GOUDA. This could be because the node attributes, rich with class-discriiinatiee information, are erased essential identification info during attacks.
Ablation Study, This experiment aims to evaluate the contribution of individual components. To be specific, it introduces two variants: one without the structure features (in Eq. 6 and another without the independence loss (in Eq. 13}. From Fig. 6 it is observable that the performance declined in both model variants compared to the complete model, which illustrates that the efficacy of GOUDA stems from the collective contribution of all components. Besides lacking Independence loss, GOUDA-IF performs inferior to GOUDA-BT, implying that InfoNCE might drive the model toward excessive

---

Cora
CiteSeer
Cora
CiteSeer
70
deAck oo4tsuu
DRANCE can OoTDWET
Ascotacc
Accurscy
10
S
GRACE GOADAOT
15
Perturbation (ate
Perturaation Kato(%)
Perturbation Rate(%)
Figure 4: Topology attack effects on GCLs.
Figure 5: Attribute attack effects GCLs.
consistency, diminishing its discriminative power.
This highlights the critical role of independence
loss in preserving diversity across augmentations.
GOUDA-IF
GOUDA-BT
GOUDA-IF
GOUDA-BT
6.5
(ccurasyP%) (
Accurscyy
Cer
Core CleSse:
80
Cleder
PulMal
75
-5
10
20
Cora
CiteSoar
PubMad
Cora
CiteSoar
PubMed
The number of AC voclors k
The number oCAC vectons
Figure 6: Contribution of individual components.
Figure 7: Impact of the number of AC vectors.
Parameter Sensitivity Analysis. These experiments are performed to offer an intuitive understanding of paper-paraeeter selection. Firstly, as depicted in Fig. 7 which illustrates performance variance for varying k GOUDA achieves consistently stable performances across (5, 10, 20). Notably, the performance variation on these datasets remains minimal, staying within 2% margin. Thus, GOUDA has low sensitivity to parameter k. Moreover, this parameter requires no significant value for GOUDA to perform well; setting as low as 5 suffices. However, a value of 1 is inadequate due to the absence of augmentation diversity. The analysis of other hyper- pppee-parameter is given in Section E.6
5 Conclusions
In this paper, we present UGA, a unified Graph Augmentation (GA) module that addresses the issues in existing GAs, including specificity, complexity, and incompleteness. Motivated by the local attribute-modifying characteristics of GAs, UGA introduces a moderate number of Augmentation- Centric (AC) vectors simulate GA impact on nodes. We further propose GOUDA, a generalized Graph Contrastive Learning (GCL) framework built on UGA. GOUDA promotes both consistency and diversity across augmentations by employing contrastive loss and an independence loss, respectively. Extensive evaluations demonstrate the generality and efficiency of GOUDA. However, the robustness analysis suggests a scope for enhancement in its robustness against attribute attacks. Future research could explore multi-modal learning methods that fuse diverse structural features into node attributes, aiming better preserve discriminative information and thus enhance robustness.
6 Acknowledgments
This work was supported in part by the National Key R&D Program of China (No. 2022/D01 19202), in part by the National Natural Science Foundation of China (No. U22B2036, 62376088, 62276187, 62102413, 62272020), in part by the Hebei Natural Science Foundation (No. F2024202047), in part by the Hebei Province Higher Education Science and Technology Research Project (No. QN2024201), in part by the National Science Fund for Distinguished Young Scholarship (No. 62025602), and in part by the XPLORER PRIZE.
References
[1] Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Comput., 15(6):1373-1366 2003.
[2] Piotr Bielak, Tomasz Kajdanowicz, and Nitesh V. Chawla. Graph barlow twins: A self- supervised representation learning framework for graphs. Knowl. Based Syst. 256:109631 2022.
10

---

[3] Chih- Chih-Chung Chang and Chih-Jen Lin. Libsvm: library for support vector machines. ACM transactions on intelligent systems and technology (TIST), 2(3):1-27, 2011.
[4] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey E. Hinton. A simple framework for contrastive learning of visual representations. In ICML, volume 119, pages 1597-1607, 2020.
[5] Fan RK Chung. Spectral graph theory, volume 92. American Mathematical Soc., 1997.
[6] Henry P Decell, Jr. An application of the hhyeey-hamiltnn theorem to generalized matrix inversion. SIAM review, 7(4):526-528, 1965.
[7] Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. In ICLR, 2022.
[8] Taoran Fang, Yunchao Zhang, Yang Yang, Chunping Wang, and Lei Chen. Universal prompt tuning for graph neural networks. In NeurIPS, 2023.
[9] Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. CoRR, abs/1993.00442 2019.
[10] Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In ICML, volume 70, pages 1263-1272
[11] Arthur Grettonn, Olivier Bousquet, Alexander J. Smola, and Bernhard Schölkopf. Measuring statistical dependence with hilbert-schmidd norms. In ALT, volume 3734, pages 63-77, 2005.
[12] Jean-Bastien 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 own latent new approach to self-supervised learning. In NeurlPS, 2020.
[13] Hongyu Guo and Yongyi Mao. ifmixup: Towards intrusion-free graph mixup for graph classification. arXiv e-prints, pages arXiv-2110, 2021.
[14] Kaveh Hassani and Amir Hosein Khas Ahmadi. Contrastive multi-view representation learning on graphs. In ICML, volume 119, pages 4116-4126, 2020.
[15] Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In CVPR, pages 9726 9726-9735, 2020.
[16] Anil K Jain and Richard C Dubes. Algorithms for clustering data. Prentice-Hall, Inc., 1988.
[17] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks, arXiv, 2016
[18] Johannes Klicpera, Stefan Weißenherger, and Stephan Günnnemann Diffusion improves graph learning. In NeurIPS, pages 13333-13345, 2019.
[19] 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, abs/2010.09891, 2020.
[20] Wen-Zhi Li, Chang-Dong Wang, Hui Xiong, and Jian-Huang Lai. Homogel: Rethinking homophily in graph contrastive learning. In SIGKDD, pages 1341-1352, 2023.
[21] Lu Lin, Jinghui Chen, and Hongning Wang. Spectral augmentation for self-supervised learning on graphs. In ICLR, 2023.
[22] Ralph Linsker. Self-organization in perceptual network. Computer, 21(3):105-117, 1988.
[23] Meng Liu, Zhengyang Wang, and Shuiwang Ji. Non-local graph neural networks. IEEE Trans. Pattern Anal. Mach. Intell., 44(12):10270-10276 2022.

---

[24] Yixin Liu, Ming Jin, Shirui Pan, Chuan Zhou, Yu Zheng, Feng Xia, and S Yu Philip. Graph self-supervised learning: A survey. IEEE transactions on knowledge and data engineering. 35(6):5879-5900 2022.
[25] Péter Mernyei and Catalina Cangea. Wiki-cs: A wikipedia-basee benchmark for graph neural networks. CoRR. 0bs/2200.02291. 2020.
[26] Zhen Peng, Wenbing Huang, Minnan Luo, Qinghua Zheng, Yu Rong, Tingyang Xu, and Junzhou Huang. Graph representation learning via graphical mutual information maximization. In WWW, pages 259-270 2020.
[27] David E Rumelhart, Geoffrey E Hinton, and Ronald J Williams. Learning representations by paok-propggating errors. nature, 323(6088):533-556, 1986.
[28) Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Gallagher, and Tina Eliassi- Rad. Collective classification in network data. Al Mag., 29(3):93-106 106, 2008
[29] Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski. and Stephan Günnemann. Pitfalls of graph neural network evaluation. CoRR, abs/1 81 .05868, 2018.
[30] Fan- Yun Sun, Jordan Hoffmannn, Vikas Verma, and Jian Tang. Infograph: Unsupervised and semi-supervised graph-level representation learning via mutual information maximization. In ICLR, 2020.
[31] Susheel Suresh, Pan Li, Cong Hao, and Jennifer Neville. Adversarial graph augmentation to improve graph contrastive learning. In NeurIPS, pages 55920-15933 2021.
[32] Shantanu Thakoor, Corentin Tallec, Mohammad Gheshlaghi Azar, Rémi Munos, Petar Velick- ovic, and Michal Valko. Bootstrapped representation learning on graphs. CoRR, abs/2102.065114 2021.
[33] Aäron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. CoRR, abs/1807 0tss/1807.00 01/1037770374. 2018.
[34] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. CoRR, abs/1710.100033, 2017.
[35] Petar Velickovic, William Fedus, William L. Hamilton, Pictro Liò, Yoshua Bengio, and R. Devon Hjelm. Deep graph infomax. In ICLR, 2019.
[36] Junran Wu, Xueyuan Chen, Bowen Shi, Shangzhe Li, and Ke Xu. SEGA: structural entropy guided anchor view for graph contrastive learning. In ICML, volume 202, pages 37293-37312, 2023.
[37] Lirong Wu, Haitao Lin, Cheng Tan, Zhangyang Gao, and Stan Z Li. Self-supervised learning on graphs: Contrastive, generative. or predictive. IEEE Transactions on Knowledge and Data Engineering, 3514):421644235, 2021.
[38] Zhenpeng Wu, Jiamin Chen, Raeed Al-Sabri, Oloulade Babatounde Moctard, and Jianliang Gao. Adaptive graph contrastive learning with joint optimization of data augmentation and graph encoder. Knowl. Inf. Syst., 66(3):1657-16811 2024.
[39] Teng Xiao, Zhengyu Chen, Zhimeng Guo, Zeyang Zhuang, and Suhang Wang. Decoupled self-supervised learning for graphs. NeurIPS, 2022.
[40] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In ICLR, 2019.
[41] Keyulu Xu. Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In ICML, volume 80, pages 5449-5458.
[42] Pinar Yanardag and S. V. N. Vishwanathan. Deep graph kernels. In SIGKDD, pages 1365-1374, 2015.
12

---

[43] Liang Yang, Runjie Shi. Qiuliang Zhang, Bingxin Niu, Zhen Wang, Xiaochun Cao, and Chuan Wang. Self-supervised graph neural networks via low-rank decomposition. In NeurIPS, 2023.
[44]
Longqi Yang, Liangliang Zhang, and Wenjing Yang. Graph adversarial self-supervised learning. In NeurlPS, pages 14887-14899, 2021.
[45] Yihang Yin, Qingzhong Wang. Siyu Huang, Haoyi Xiong, and Xiang Zhang. Autogel: Auto- mated graph contrastive learning via learnable view generators. In AAAI, pages 8892-8900, 2022.
[46] Jiaxuan You, Rex Ying, and Jure Leskovec. Position-aware graph neural networks. In ICML, volume 97, pages 7134-7143, 2019.
[47] Yuning You, Tianlong Chen, Yang Shen, and Zhangyang Wang. Graph contrastive learning automated. In ICML,, volume 139, pages 12121-12132, 2021.
[48] Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. In NeurIPS, 2020.
[49] Jure Zbontar, Li Jing, Ishan Misra, Yann LeCun, and Stéphane Deny. Barlow twins: Self- supervised learning via redundancy reduction. In ICML, pages 12310- 10-12220.. PMLR, 2021.
[50] Hengrui Zhang, Qitian Wu, Junchi Yan, David Wipf, and Philip S. Yu. From canonical correlation analysis self-supervised graph neural networks. In NeurIPS, pages 76-89, 2021.
[51] Tong Zhao, Gang Liu, Stephan Günnemann, and Meng Jiang. Graph data augmentation for graph machine learning: A survey. CoRR, abs/2202.08871, 2022.
[52] Tong Zhao, Yozen Liu, Leonardo Neves, Oliver Woodford, Meng Jiang, and Neil Shah. Data augmentation for graph neural networks. AAAI, volume 35, pages 11015-11023, 2021.
[53] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep graph contrastive representation learning. CoRR, abs/2006. 04111, 2020.
[54] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Graph contrastive learning with adaptive augmentation. In WWW, pages 2069-2080, 2021.
[55] Jiaming Zhuo, Can Cui, Kun Fu, Bingxin Niu, Dongxiao He, Yuanfang Guo, Zhen Wang, Chuan Wang, Xiaochun Cao, and Liang Yang. Propagation all you need: new framework for representation learning and classifier training graphs. In MM, pages 481-489, 2023.
[56] Jiaming Zhuo, Can Cui, Kun Fu, Bingxin Niu, Dongxiao He, Chuan Wang, Yuanfang Guo, Zhen Wang. Xiaochun Cao, and Liang Yang. Graph contrastive learning reimagined: Exploring universality. In WWW, pages 641-651, 2024.
13

---

A Algorithm Description
To demonstrate the broad applicability of the proposed framework GOUDA, this paper implements two models, namely GOUDA-IF and GOUDA-BT. Specifically, GOUDA-IF employs a prevalent node-level contrastive loss ( (ie. InfoNCE), while GOUDA-BT utilizes feature-level contrastive loss (i.e., BarlowTwins)) GOUDA-IF is illustrated as an example to describe the entire algorithm, as presented in Algorithm [ Accordingly, GOUDA-BT can be described by substituting the contrastive loss Leontrast (,) in line 3 of this algorithm.
Algorithm 1: GOUDA-IF
Input: graph (A, X), hyperparameters ",, B1, B2 and т.
Output: node representations H(2) E RRa and H E Raxd
Initialization: graph encoder ge(,), ) projection heads g(-). and the matrices of Augmentation-Centte (AC) vectors Q E / and P E R
while not converged do
% Augmentation %
1. 91 + t(G, Q) and G2 + LG, P) via Eq. 6 and Eq.
% Encoding %
([2) +- (91) and H ge (92) via Eq. 2
% Calculating loss %
C + Coontrasa HH
(1) ( + 7 Cindep Q P) via Eq. 13
% Optimizing %
4. θ < Adam(L, 9):
end
return (()) E Rexd H2 E Raxd and ge(:);
B Introduction of Graph Augmenations
Categorized by the type of graph information they manipulate, Graph Augmentations (GAs) can be broadly divided into four categories: node augmentation, edge augmentation, attribute augmentation, and subgraph augmentation. The detailed introduction and examples given below.
Node Augmentation. This augmentation generally creates the new graph by dropping or adding the perturbated nodes and the edges that connect to these perturbated nodes of the input graph, as
shown Fig. D [). Employing the adjacent matrix to formally represent the graph topology, the edge
augmentation can be denoted by (A (+), x()).. Therefore, these can be formulated as
Node Dropping:
X + (V/V,8/E) X/X ( X (VUD,EUE) X|X,
A
(14)
Node Adding
(15)
where 1 denotes the perturbated node set, X stands for the attributes of these nodes, and & terms the set of edges connected these nodes. The operator is widely used graph classification [48 47
Edge Augmentation. Unlike node augmentation, the edge augmentation, denoted by G. X). exclusively operate on edges. It involves either removing perturbated edges from or adding perturbated edges to the input graph, as indicated in Fig. [bb.. These can be expressed as
Edge Removing (+) + (Σ/E)
(16)
Edge Adding A - (E
(17)
where E represents the set of perturbated edges, which is randomly determined [53 adaptively learned (3I] during each training epoch.
54
32
20 or
Attribute Augmentation. Typically, the attribute augmentation (expressed by (A x()) gener- ates the new graph by masking (in Fig. [c) or corrupting the raw node attributes. These can be described as
Attribute Masking:
( X & M
(18)
Attribute Corrupting
X X. + S,,
(19)
14

---

where M E Rax stands for the mask matrix and ó, terms the noise vector for node v, which is updated iteratively by adversarial training 19 44
Subgraph Augmentation. As typical graph-level operators, the subgraph augmentation crops out subgraphs (in Fig. d)) inserts additional subgraphs create graphs, follows
Subgraph Cropping G.(A (()) G
(20)
Subgraph Inserting: G.(A (()))))))) - g/
(21)
where (AA, X) stands for the perturbated subgraph. The subgraph augmentation mostly used for graph-level tasks [3]
C Introduction of Graph Contrastive Losses
The contrastive loss serves as crucial technique that enhances data representation through discrimi- nation. Generally, it operates on two levels of representation matrices: the sample level [3], where it aligns the representations of positive samples and uniformly distributes all representations, and the where it targets reducing redundancy between features.
feature level 49 2
Sample-level contrastive losses. the nascent stages of research, the designs of contrastive losses inspired by the success of contrastive learning (CL) in computer vision (CV) 4 To be specific, this type of contrastive loss aims to minimize the distance between the anchor sample and positive samples while maximizing the distance between the anchor sample and negative samples [33] As
a typically sample-level contrastive loss, InfoNCE loss [33] classifies the embeddings of the same node from different views as positive samples while treating the embeddings from all other nodes as negative samples. This loss can be formulated as
LinfONCE
Σ
((h()) h. + l(h,)) h("))
(22)
4(b2 //7)
where l (n6,,, h1.3) = -log
(23)
4 h e
4 (1 Au!
Σ NEV
Σ
WEV, use
where (h,,, h..) = s (g(h)) (hh)) stands for the feature similarity function, and g(+) represents the projection heads [4), and 8(.) terms the consine similarity. t denotes the temperature coefficient.
Feature-level contrastive losses. This type of loss is designed to directly optimize contrastive losses the feature space, bypassing the need for defining explicit positive and negative samples, thus overcoming sample selection challenges. Barlow Twins (BT) 49 and CCA-SSG (50) are two notable approaches aimed at improving feature representation learning by minimizing redundancy between feature dimensions. BT enforces the mutual information matrix computed the features from two different views to approximate the identity matrix, ensuring that the learned representations are free from redundant information. This can be formulated as
f-1
f-1--1
EvEV Bugi hus
CBarlowTwins
(1-c..) X
2 (c,)),
C. = EVEE / Evee(hoo))
(24)
1=0
I=
where À denotes a hyperparameter to tradeoff two terms.
CCA-SSG not only pushes the covariance matrices from each view to approach an identity matrix but also enhances feature consistency across views to learn informative representations of both unique and shared data characteristics.
D Theoretical analysis
D.1 Proofs for Theorem 3.1
For the sake of clarity, us briefly describe the whole process. Firstly, the proof proceeds from the premise of one-layer graph encoder without activation functions. For node-level tasks, the graph
15

---

encoder ()) is configured as a one-layer GCN, For graph-level tasks, ge(:) is set as one-layer GIN with a sum pooling sum(-). Subsequently, the obtained conclusions are generalized to the case of multi-layer encoders.
Specifically, for the one-layer graph encoders, the encoding process for node representations (H) and graph representations (h) can be expressed as
Node representations:
H GCN (A, = - W
(25)
Graph representations:
sum A, X)) sum ((A (1++ X W), (26)
where À = DDD-E AÁD= denotes the normalized adjacency matrix and e terms an learnable parameter.
In the proposed UGA implementation, both node and graph representations can be decoupled into two terms: the original representations (represented as H and h), which can be regarded directly calculated from Eq. 2nd Eq. [26] respectively. and the augmented representations (denoted as AH and Ah9). To be specific, two terms the node representations can expressed
H GCN (A, x QQ
A Q) W
(27)
A W + A Q-Q. W
H + AH
Similarly, two terms of the graph representations can be described as
h sum (GIN (A,X+ +
sum ((A + (1 [1+ (1 (X + Q) W)
(28)
sum ((A + e1++ W) sum ((A + (1++) Q W)
= h + Ah"
Next, establish Theorem 3.1 Lemma D.I is introduced.
Lemma D.1. For any GA t(.) applied to the imput graph G(A,X), it can be decoupled to series of three augmentations: attribute augmentation (t, (X)), edge augmentation (te(A)), and subgraph augmentation (A, ()) containing node augmentation [8].
Accordingly, the candidate spaces (i.e., A and X) can be created through these three augmentations. Theorem 3.1 can be proven based on this lemma by establishing the following three propositions.
Proposition D.2. From the message-passing perspective of the graph encoder ge(,) ), the proposed implementation of UGA, which is expressed Eq. can be equivalent to any attribute augmentation to (X), that is
ge A, X Q (A,((A(()))
(29)
where (+) (X) stands for the augmented node attirbutes.
Proof. Firstly, let us discuss the equivalence for node representations. To establish Eq. 29 the goal is to identify Q such that H H Let 4X X (-) denote the variance in attributes resulting from attribute augmentation, H can be decomposed into two terms: the original representations H and the augmented representations AH. This decomposition can be expressed as
H GCN (A, AX)
(X+
(30)
= W + À AX. W
-H+ -H+AH.
Therefore, the proof shifts from establishing H He to demonstrating AH AH", It becomes evident that this equivalence holds true under the condition 4.j Ar. thus ensuring that ÁQW ÁAXW.
Moreover, this derivation highlights that the conclusion remains consistent regardless the encoder chosen. Henee, the solution 4. Aæzy holds for the node representations encoded using GIN.
16

---

Besides, the conclusions drawn at the node level, unaffected by the choice of readout functions (e.g., mean and sum), are equally applicable to the graph level. This insight extends our solution to graph representations h, thereby completing the proof.
Proposition D.3. From the message-passing perspective of the graph encoder ge()). ). the proposed implementation of UGA, which is expressed as Eq. 4 can be equivalent to any edge augmentation te (A), that is
ge (A, Q) ge (A (x),
(31)
where (+) (A) denotes the adjacency matrix obtained from edge augmentation.
Proof. Consistent with the method adopted in the above proofs, the adge-augmented representations (H" and h²) are first computed. Next, the equivalence of these representations with UGA counterparts (H" and h"), respectively, is demonstrated.
Let 4A = A - A denotes the topology variance caused by edge augmentation, H can be decoupled into two terms as follows.
H GCN (A + AA
(A+AA X W
(32)
A W AÁ W
= H AH.
where AÀ = Á- (+) terms the topology variance between the adjacency matrix and its augmented version, both of which normalized. Therefore, this demonstration solely necessitates establishing the equivalence between AH, and AHe, particularly
A A W - W.
(33)
Through the utilization of Camley-Hamilton theorem 6 which asserts that every matrix adheres its own characteristic polynomial, that
T(A)= A + c2 n- n- + G, =
(34)
where {ct} stands for the set of polynomial coefficients. Thus, the inverse of matrix Á can be expressed as
Ä A-1 1 A n- C n-2
Ca-li I.
(35)
Based on it, the equivalent between the proposed UGA and edge augmentation (denoted Eq. 33 can be demonstrated if holds that
Φr. = [(
A
n-
C1 A n- Cn-11) I) A
-
(36)
Cn
Cn
Furthermore, the solution derived for node representations is directly applicable graph representa- tions as well, with the sole modification being the substitution of A with A + (1 eI). In light of the above analysis, this proposition proven.
Proposition D.4. From the message-passing perspective of the graph encoder ge(,), the proposed implementation of UGA, which is expressed as Eq. 4 can be equivalent to any subgraph augmentation to (A, X), that is
8e = (A (x))))))
(37)
where A (+) subgraph augmentation.
(+) = (A, X)
stand for the adjacency matrix and attribute matrix obtained from
Proof. Note that the subgraph augmentation is typically tailored for graph-level tasks. For node-level tasks, specific subgraph augmentation (where the number of nodes remains unchanged) can be regarded as type of edge attribute augmentation, such as masking all attributes of nodes in the
17

---

perturbated subgraph. Hence, based on Proposition| D.2 and Proposition D.3 it is not hard to conclude that this proposition holds.
Recall that within our UGA, the graph representation hy E Rixd xd is articulated as hg = h + Ahg-
This can be formulated
h sum (GIN (A,X X Q)) sum ((A + (1 (1+))T) X W) + sum ((A + (1+))I) Q W)
(38)
+ Ah
Furthermore, let us assume that the original graph encompasses subgraphs. The corresponding subgraph-augmenter graph, in turn, encompasses subgraphs, which can be formulated as
Ao
0
0
X
A 1
0
X
X
(39)
:
Am-
X
where A, denotes the adjacency matrix of the i-th subgraph and X; terms the corresponding attribute matrix. Thus, for the augmented subgraphs {G( (A,, { the graph representation h can be formulated
h
Sum (amn((,))) (A, + (I++ X, W), -.,,),
(40)
t=0
Let Ah = h² - denotes the representation variance caused by subgraph augmentation, there is
Ah
Ω sum (1 + +)T) X, W);
(41)
where Q denotes an indicator vector. m < the subgraph augmentation typically refers the
subgraph corrupting (denoted as Eq. 20). Thus, for the 1-th perturbated subgraph, there is Q2 = -1.
And if m 1 k, generally understood as the subgraph inserting (formulated Eq. 21). Qr 1.
Additionally, if the subgraph is not changed, Ω = 0.
Next, aim to identify solution for that satisfies the following conditions:
hh Ah.
(42)
This can be further formulated as
m-1
sum ((A + (1+ Q W)
Σ
Q sum ((A, + (1++) X, W)
(43)
= =d Q-Q W Σ Ω sum ((Ar + (1+ X.) W,
where d = |do
E R stands for degree vector.
In the general case, assuming the absence of isolated nodes within the graph, the degree vector d of the input graph is devoid of zero elements. Consequently, a solution for Q can be formulated as
Q D
(44)
where A = Em m- Ωr sum((A + (1++))) X,) and D = a denotes the Moore- Penrose pseudoinverse of d. Thus, equivalence be established if each element q. in AC matrix Q satisfies the following condition:
D
sum ((A, + (1+ eI) X.)las-
(45)
Therefore, the proof ends.
18

---

Extension to multi-layer graph encoders. Following the discussion on single-layer graph encoders, solutions for multi-layer graph encoders are identified. Initially, as discussed in [18), various GNNs can be formulated as
= WW
(46)
where S denotes the diffusion matrix, exemplified by A for GCN and A + (1 + e)I for GIN. In addition, W represents the projection layer, such as the linear projection utilized both GCN and GIN. Here, the nonlinear activation function between layers is not considered. With this architecture, the node representations at the k-th layer can be formulated as
H (S,
(S X) S X.X.W. W,
(47)
where S S= -
i0 S' terms the product of adjacency matrices. Similarly, W = = W represents the product of linear projection matrices. Given that the aforementioned conclusions are independent of the forms of these two matrices, it is not hard to prove that by substituing A and W with S and W in Eq. 25 and Eq. 26 respectively, Proposition D.2 D.3 and (.d)D.sstt still hold true.
D.2 Proofs for Theorem 3.4
Proof. Firstly, note that two augmented graphs are from the same input graph ( X) without loss of the information in this graph (especially the edges and attributes). Therefore, there is (1) = (2) and (1) = x(2), Accordingly, the diversity can be transformed into
Dæ 11
Σ
(x
(1)
+ qr.))
Σ
(2) (x + +
(48)
IEN.UP
BEA.UP
= ||
Σ
Pe.:
Σ
(49)
tEN
tENoUe
=
Σ
Q
Σ
(50)
LEN
tEAL
Given the conditions
bj. a(x QT) where denotes the softmax function, we can calculate that
D. Σ b Q
Σ
PIP
(51)
IENoLU
tENoJo
||
Σ
a(x)
Q
Σ o
(x
2 P
(52)
KEN.UP
IEN
|I( Σ
ax 11)
))Q
(
Σ
(x
( P P)
(53)
tENoUV
For clarity, Xx,; is employed to represent both x and within the GOUDA framework, the difference between Q and P is minimal, which can be interpreted as a minor perturbation A, such that Q = P A. Therefore, Eq. 53 can be further reformulated as
x In light of the consistency constraint
D. = 11( Σ
X )QQ -Q
X1. PII
(54)
JEALUU
LENGUP
=I( Σ X P
(A)
Σ PPIP
(55)
1EN,Uv
tEN,Uv
Given that A is considered to be small, the terms 2 and AT can be neglected. Moreover, it can be assumed that the product of xr, A with P and A is insignificant in comparison to the other terms. Hence, the above formulation can be simplified as
D. ~ I1 Σ
(56)
tEN.UP
Since (ErEN.uX PT) is constant matrix, it can be factored out, resulting in:
D, R ( Σ Xt.
VEN.Uv
(57)
( Σ x P T)2 -P1
rEN.Uv
19

---

Hence, taking into account that (E uu Xt, PT). serves the proportionality constant, which depends on the values of Xt,; and P, we can deduce that
D. R QQ - PI
(58)
Based on the above analysis, we conclude the proof.
E
Experimental Details
E.1 Introduction of Datasets
Datasets for node-level tasks.
Citation networks [28]: Cora, Citeseer, PubMed. Each node in these networks represents scholarly article, with edges indicating citation relationships. Nodes are defined by attributes such abstracts, keywords, full-text content, and derived features like TF-IDF vectors. Labels to which nodes belong, typically corresponding to research areas or topics.
Reference network [25 Wiki-CS. This network represents a collection of Wikipedia articles in computer science. Each node corresponds to an article, characterized by its text and hyperlinks, while the edges depict hyperlinked references between articles. Node labels denote specific subfields of computer science covered by the articles.
Co-purchase networks 29 Amazon Photo (Photo for short), Amazon Computers (Com- puters for short). Nodes represent products available for purchase, with attributes such as features, prices, and customer reviews. Node labels correspond to product types or brands, while edges indicate co-purchase relationships, reflecting the frequency of items commonly bought together by customers.
Co-author network [29]: Coauthor Physics (Physics for short). Nodes represent physicists, each described by their publication record, research interests, and affiliations. Labels indicate distinct areas or subfields within physics. Edges between nodes stand for collaborations, typically formed through joint publications co-authorship of scientific papers.
Datasets for graph-level tasks.
Collaborative movie networks 42
IMDB- BOOB-BINARY (IMDB-B for short) and IMDB- MULTI (IMDB-M for short), Nodes denote actors or actresses, and an edge exists between two nodes if the individuals have co-starred in the same film.
Scholarly collaboration network [42] COLLAB. Researchers as nodes and edges indicate partnerships between them.
It is important to mention that node attributes are absent in the three datasets for graph-level tasks, making one-hot encoding of the degree typical approach.
We source these datasets from the public repository Py PoTchh Geometric (PyG) 9 The datasets can be accessed through the URLs listed below:
Cora, CiteSecr, PubMed: http://gthhhluuuukknnuuog/gaaaah
Wiki-CS: hhw.:h/wwww..iiiooooooooooooooaa
Photo, Computers: http:///ww///inooooo///////////n
Physics: http://sshhttlooooooooooooooooor IMDB-B, IMDB-M, http://www......///////////////.
kerneldatasets
E.2 Dataset Splitting
For the seven benchmark datasets utilized for node classification tasks (Cora, Citeseer, PubMed, Wiki- CS, Computers, Photo, and Physics), the dataset is divided into training, validation, and testing sets in the ratio of 1:1:8. For the three benchmark datasets employed for graph classification tasks, namely IMDB-B. B, IMDB-M, and COLLAB, 10-fold cross-validation approach is adopted to partition.
20

---

Table Statistics of ten graph benchmark datasets.
Node-lever tasks
Graph-level tasks
Cora
CiteSeer
PuhMed
Wiki-CS Computers
Photo
Physies
IMDB-BB IMDB-M COLLAB
Graphs
1
1,000
1,500
5,000
Nodes
2,708
3,327
19,717
11,701
13,752
7,650
34,493
19.8
13.0
74.5
Edges
5,429
4,732
44,338
216,123
245,861
119,081
991,848
193.1
66.0
4914.4
Features
1,433
3,703
500
300
767
745
8,451
Classes
7
10
10
8
5
3
E.3
Introduction of Baselines
Baselines for node-level tasks. Details on the baselines for node-level tasks are outlined below.
It is representative Graph Neural Network (GNN) that utilizes spectral and spatial strategies to perform graph convolutional operations. makes each node aggregate information from its neighbor nodes by integrating the graph topology and node attributes.
GCN 17
GAT [4]:
introduces an attention mechanism into the GNN, enabling each node to weigh the importance of its neighbor nodes during the aggregation process.
Unsupervised baselines detailed below.
Infomax principle-based GCL augments the graph row-wise shuffling of the attribute matrix and maximizes the mutual information between global and local representations.
DGI
35
GMI 26 is variant model DGI that maximizes comprehensive graphical mutual information metric, including features and edges between nodes in both the input and reconstructed output graphs.
MVGRL [4] It is variant model of DGI, employing contrastive learning between various structural views of graphs, including first-order adjacency and graph diffusions.
GRACE 153 It is GCL model that generates node embeddings by corrupting both graph structure (via random edge removing) and attributes (via random attribute masking) to create diverse views and maximize their agreement.
GCA [54]:
variant model GRACE, which incorporates adaptive augmentation strategies based on node centrality, aiming to enhance the flexibility of the model.
BGRL 32 It is GCL model that augments the graph through random edge removing and employs bootstrapping to update the parameters of the online encoder.
GBT 2 A feature-level GCL model leverages the validated Barlow Twins loss for training, aiming to reduce redundant information between two views obtained through random edge removing.
CCA-SSG [50]: It is a GCL model utilizing feature-level contrast derived from Canonical Correlation Analysis (CCA) to learn the node representations.
SPAN 21: introduces a spectral augmentation scheme for topology augmentation by perturbing the graph spectrum, and aiming to maintain spectral invariance to sensitive structures, and minimizing graph spectrum changes.
DSSL (39]
It is graph self suff-supervised model that presents an approach that disentangles the varied neighborhood contexts of a node, aiming to model multifaceted information within the graph.
a localized variant model of GRACE, incorporating k-mean-based saliency values weigh the importance of neighbor nodes.
HomoGCL 20:
Baselines for graph-level tasks. Introductions of the baselines for graph-level tasks are given below.
InfoGraph 30 It is a variant of DGI, which maximizes mutual information between graph-level representations and substructures at different scales, such as nodes, edges, and triangles.
GraphCL [48]: It is a GCL framework that learns graph representations by employing various augmentation techniques the local subgraphs of nodes.
JOAO 47 : It is variant GraphCI, which utilizes the min-max optimization automatically select the most effective GAs during the contrastive learning process.
21

---

AD-GCL [I: It is GCL framework based on adversarial training, introducing an attack process to modify the edges.
For the baseline inplementations, we utilize PyG to implement GCN and GAT. In addition, for the self-supervised baselines, we employ their source codes. The sources are listed below:
GCN, GAT: httpp///ww....oooo.....o.......r /nn/conv
geometrie
DGI: http:://gggtuuu..moo///a/aa/llll GMI: httpps///ggghuubbooo//////////// MVGRL: MVGRL: htggg///h/g/gghiu.oooo/////aaaaa
GRACE: http://gghhuuccom//////cccCCCCCC
GCA: http::/s/gghuubboooooc/cccccCcC
BGRL: http::/ggihhua.ccom///ecdaaababl
GBT: http:///sthbbbboooo//cca///////s
SPAN: http:///gstiiiicooomo/oo//g////a
DSSL: http:////wsss.iicc.oooooooo/////
InfoGraph: http:///shhuu..com////aayyyynanf
GraphCL: http:////ghhhhbboooo/////eaaaaaa
JOAO: http:://iihaaaconSSSSeaaaalaalla
AD-GCL: https//ggthubbbcoo/uuussealaggl
E.4
Complexity Analysis
This subsection analyzes the complexity of GOUDA in comparison with the baseline GCL equipped with learnable GAs (i.e., SPAN, JOAO, and AD-GCL). Note that since the updates of these GCLs can utilize the same graph encoder (e.g., GCN) and contrastive loss (e.g., InfoNCE loss), this discussion focuses solely on the time complexity of the augmentation phase.
To enhance clarity, us define our terms: n represents the number of nodes corresponding to network size; signifies the number of edges; f refers to the dimension of attributes; and d denotes dimension of the hidden layers.
SPAN [1 The time complexity for augmentations in SPAN is O(n²tk), where t denotes the time of iterations and is the number of eigenvalues be selected. Specifically, SPAN necessitates an iterative optimization of the augmentation through eigen-decompositton. which demands Ott)²) complexity. Nonetheless, this complexity can be reduced to (n?tk) by employing selective eigen- decomposition on the & lowest- and highest-eigenvalle via the Lanczos Algorithm.
The time complexity for augmentations in JOAO O(n²d) d). Specifically, JOAO employs a min-max optimization strategy to refine the parameters that are used for selecting augmentations from an option pool. This process involves maximizing the contrastive loss, which inherently requires a O(n2d) d) complexity.
JOAO 47
The time complexity for augmentations in AD-GCL is O(nad). Similarly, AD-GCL employs min max optimization strategy, but its objective is to modify edges. Therefore, this process also entails maximizing the contrastive loss, which carries a O(n" complexity. In addition, encoding edges is required, which introduces a complexity of (mm??).
AD-GCL B1:
The time complexity for augmentations in the proposed GOUDA is O(nkf). GOUDA introduces k AC vectors to nodes and utilizes the consistency-diveriiyy balance principle to update these AC vectors, where k & n. Firstly, nodes are updated by aggregating the features of AC vectors, which incurs complexity of O(nkf). Besides, GOUDA maintains consistency by minimizing the contrastive loss, process inherent to the training model and thus does not introduce additional
GOUDA
22

---

complexity; to ensure diversity, it calculates the independence loss, which brings in a complexity of O(k²f), f). Therefore, the overall complexity O(nkf).
In summary, GOUDA presents a more computationally efficient approach than the baselines, which is supported by the evidence presented in Section 4
E.5
Configurations and prreeppprameters
E.5.1
Configurations
The experiments leverage the linear evaluation method [26), where models are firstly trained in an unsupervised manner, and then, the obtained embeddings are utilized for downstream tasks. For the node-level tasks, the graph encoder Ke is configured as two-layer GCN [7], while for the graph classification tasks, it is set as five-layer GIN [40] In the evaluation phase, we utilize a single-layer linear classifier [27] for node classification (26). apply K-means [T6] to node embeddings for node
clustering, and train an SVM classifier [3] for graph classification. The results for node-level tasks
the average of ten random runs, while those for graph-level tasks are based on five runs.
E.5.2 Environment
All experiments are conducted on two Linux machines as shown in Tab.
Table 6: Experimental environment servers.
Server
Server 2
OS
Linux 5.15.0-82-generic
Linux 5. 5.1.00-1000 -00generi
CPU
Intel(R) Core(TM) i7- 12700K CPU @ 3.6GHz
Intel(R) Core(TM) 19- 19-10980XE CPU @ 3.00GHz
GPU
GeForce RTX 4090
GeForce RTX 3090
E.5.3
Hyper-parameter Settings
GOUDA is implemented as two models: GOUDA-IF, which utilizes InfoNCE loss, and GOUDA- BT, which employs BarlowTwins loss. For the node-level tasks, both models are trained using an Adam optimizer with learning rate of 1e-3 and the weight decay rate from {0, 5e =3. The dimensions of node embeddings are selected from (256, 512, 1024. 2048]. and their impact is analyzed in Section 4.2 The hyperparameters B1 and 33 of independence loss are chosen from {le 1e-3), 33, while the related hyperparameter 7 selected among {le 1e
10). Addition- ally, for GOUDA-IF, the temperature coefficient is selected from {0.2, 0.4, 0.6, 0.8). while for GOUDA-BYS the hyperparameter À is set 1
z. For the graph-level task, the configuration follows GraphCL. 48] where the hidden dimension is fixed to 128 and the penalty parameter of SVM is selected from {le le -2, le 1e2, les) The choice of threshold is given Section E.6.2
E.6
Additional Experiment Results
E.6.1
Complete Results for Node Clustering
Tab. presents the comprehensive results of the node clustering experiments. The analysis of these results can be found in Section
E.6.2 Other Hyperparameter Analysis
This experiment aims to shed light on the selection of hyperparameter d. As depicted in Fig. 8 the proposed GOUDA shows improved performance with an increased embedding dimension. Notably, GOUDA-IF IF and GOUDA-BT exhibit reduced performance at an embedding dimension of 256 compared to higher dimensions. This indicates that a large embedding dimension is essential for contrastive learning models to capture robust representations. Moreover, it is observable that there a slight decrease the performance of GOUDA-IF with large dimensions. This can be due to overfitting the self-super signal, which may hinder its generalization capability.
Embedding Dimension.
23

---

Table Node clustering performance: NMI ARI Scores in percentage (mean
Cora
CiteSeer
PuhMed
NMI
ARI
NMI
ARI
NMI
ARI
DGI
52.75
47. 47.78-20.5
40.43
41.84 41.84g0 62
30.03
29.7840.28
MVGRL
54.21
49.0410.67
43.26 23.24....8
42.73
30.7510.54
30.4210.45
GRACE
54.50=0.32
48.31
43. +2.433
42.32=0.81
31.11=0048
30.37+0.51
GBT
50.3220065
48.91 +0.73
44.01 +0.97
42.61
31 +0.33
30.6440.74
CCA-SSG
56.3820.62
50.62.00.0
43.9840.94
42.7920.77
32. 32.06
31.1540.85
GOUDA-IF
57.92
52.41 =0.68
45.11 40.79
43.8240.05
33.17 +0.46
31.98
GOUDA-BT
57.35
51.84
44.93
43.46ga0.1
33.14
31.73
GOUDA-IF
GOUDA-BT
GOUDA IF
GOUDA BT
Ascurayy
Care CleSen
Cor
Conh Clzseer
Avcomeeyye
Can
80
Choller
CloSeer PAMaJ
PalMod
13
75
256
$12
1034 d
2046
256
$12
1004
20468
0.01
0.1
0.01
10
Dimension
Dimension
Hyper-porameter V
Hyper-garametor
Figure 8: Impact of dimension d.
Figure Impact of hyperparameter 7,
Weight of Independence Loss. Several insights are yielded from observations in Fig. Firstly, the proposed GOUDA shows stability regardless parameter ? changes. Secondly, the framework maintains robust performance even at low value of 0.01 and 0.1. However, the omission of the proposed Independence loss does have a detrimental effect, as demonstrated by the Ablation Study (in Section 4.2) Lastly, while the tested parameter range is {1, 10). future research should consider broader or more detailed ranges.
Threshold for sparsification.
The performance changes resulting from varying the hyperparameter are detailed in Tab. [ To eliminate bias due to network size, e is not freely tuned. Instead, set as the output of the selection function selection (B, 8). which estimates this threshold. B denotes the matrix of propagation weights from AC vectors to nodes, and stands for the proportion of the largest elements retained. The value of is chosen from the set {0.2, 0.4, 0.6, 0.8} in the experiments. From Tab, S it can be observed that the threshold does not significantly affect the model performance. Specifically, within the range of selection, the variation in model performance does not exceed 2%.
Table 8: Impact of threshold e.
GOUDA-IF
GOUDA-BT
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
Cora
85.29
84.71
84.19
86.11
85.07
84.56
85.88
85.99
CiteSeer
74.55
73.20
73.11
73.62
74.34
74.47
73.98
73.41
PubMed
86.96
87.25
87.55
87.05
87.59
86.94
86.76
87.11
24

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction clearly outline the contributions our paper, including the motivation and design of the UGA module and the GOUDA framework.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We have discussed the limitations within the Conclusion, particularly regarding our model's robustness to attribute attacks. We have outlined potential directions for future research to address these concerns.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g. independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
25

---

Answer: [Yes]
Justification: All theoretical results are accompanied by clearly stated assumptions and complete proofs, provided in the main paper and referenced appropriately.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The supplemental material contains a zip file of our model's code, enabling the replication of the experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
26

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We have included complete and executable code within the supplemental material, ensuring the reproducibility of our results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://niis.cc)
Moolicc/uuides/Coeeetuliiis catssiionoolyyy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips. wwtps/cccppppclgguiuaeeeaeccuuea
Saaeee/CCoSSSubisss..S.. www.sssoiccgyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We have provided detailed descriptions of our experimental setup in Section including data splits, hyperparameters, and optimizer, etc.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We have reported error bars representing the standard deviation of our experi- mental results (e.g., Fig. 6).
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
27

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g., negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We have provided the computational resources used for all experiments in Section E.5.2
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: Our research adheres to the NeurIPS Code of Ethics, and we have ensured that all aspects our work.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consider- ation due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Due to the nature of this work, there may be no potential negative social impact that is easily predictable.
Guidelines:
28

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negatíve societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles. surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g.. gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: Our work does not involve releasing data or models that pose a high risk for misuse, so specific safeguards necessary.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We have accurately credited the sources and provided URLs in Section E. and Section
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
29

---

For scraped data from a particular source (e.g., website), the copyright and terms of service of that souree should be provided.
If assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, papprswi thcode. com/ com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
The supplemental material includes the zip file of our code.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/mooel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing or research with human subjects, this information is not applicable.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This research does not involve human subjects, so IRB approvals or equivalent reviews are not required.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
30

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
31


Reviews:
[{"review_id": "SxrFcCGHxv", "reviewer": "Reviewer_i3ih", "summary": "The paper introduces GOUDA, a versatile framework for Graph Contrastive Learning that addresses the limitations of existing graph augmentation techniques. GOUDA proposes a unified graph augmentation module capable of simulating various explicit graph augmentations, enhancing the generality and efficiency of GCL models. By incorporating both widely-adopted contrastive losses and a novel independence loss, GOUDA ensures consistency and diversity across different augmentations.", "questions": "1. How to interpolate the learned AC vectors? \n2. How is k selected in line 181?\n3. Graph augmentation is based on the assumption that the augmentation does not change the original class label, how does UGA guarantee this?", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The paper addresses a crucial problem in graph contrastive learning: the specificity, complexity, and incompleteness of current graph augmentation techniques.\n2. The paper conducts experiments on multiple datasets and compares the results with various baseline models.", "weaknesses": "1. Some of the mathematical derivations and formulas are complex and may be difficult for readers to follow. Although the notations are defined, the paper could provide more intuitive explanations and step-by-step derivations to enhance understanding.\n2. While authors have compared with many GCL methods, the comparison with GA techniques like simple node augmentation is missing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "***Q1. The paper could provide more intuitive explanations and step-by-step derivations to enhance understanding.*** \n\nR1. Thanks for your valuable suggestion. We will further clarify the mathematical formulas with intuitive explanations in the revised manuscript. Besides, please refer to the Appendix for detailed derivations.  \n\n---\n\n***Q2. While authors have compared with many GCL methods, the comparison with GA techniques like simple node augmentation is missing.*** \n\nR2. Simple node augmentation has been compared in our experiments since it is the augmentation strategy employed by many existing GCL methods, such as GraphCL [1]. Specifically, GraphCL employs random node dropping, a prevalent and simple node augmentation strategy, in the augmented graph construction. Following your suggestion, we will clarify this in the revised version. \n\nFigure 3 shows these comparisons from both effectiveness and efficiency perspectives. For convenience of review, the total accuracy and the running time for each training epoch are given as follows. \n\n| Accuracy(%) / Time(s) | IMDB-BINARY  | IMDB-MULTI |\n|:--------| :---------:|:--------:|\n| GraphCL | 71.14 / 0.49 | 48.58 / 0.56 |\n| GOUDA-IF (Ours) | 75.22 / 0.41 | 52.43 / 0.47 |\n| GOUDA-BT (Ours) | 76.80 / 0.46 | 53.05 / 0.55 | \n\nIt is evident that GOUDA not only achieves superior performance but also possesses efficiency similar to GraphCL. This highlights that GOUDA is a lightweight yet highly effective framework. \n\n[1] Graph Contrastive Learning with Augmentations. NeurIPS 2020\n\n---\n\n***Q3. How to interpolate the learned AC vectors?***\n\nR3. The AC vectors are interpolated via a graph-based strategy. Besides the nodes in the original graph, AC vectors are treated as another type of nodes in the new graph. The additional connections (i.e., edges) from AC nodes to the original nodes are constructed according to the feature similarity, as formulated in Eq. 6. This interpolation strategy benefits both the reduction of the tuning parameters for graph augmentations and the flexibility by dynamically adjusting the varying importance of relationships. \n\n--- \n\n***Q4. How is k selected in line 181?*** \n\nR4. We recognize your concerns about the selection of the $k$, which is a key hyperparameter in the proposed GOUDA. The proposed framework sets $k$ as a small number, which is independent of the size of the graph. The submitted manuscript has presented an experimental assessment of the impact of varying $k$ on model performance, as shown in Figure 7, where $k$ is selected from the set {1, 5, 10, 20}. Our observations indicate that GOUDA is relatively insensitive to the hyperparameter $k$ as explained in Section 4.2. Therefore, one need not be overly concerned with the precise value of $k$ for GOUDA’s robustness to changes in $k$. \n\n---\n\n***Q5. Graph augmentation is based on the assumption that the augmentation does not change the original class label, how does UGA guarantee this?*** \n\nR5. Note that NO data augmentation can guarantee semantic invariance in self-supervised learning since label information is unavailable. All the augmentation-based graph contrastive learning methods are based on the assumption of local smoothness in the space of graphs, and thus, slight changes between original and augmented graphs do not change the semantics, i.e., the label, of the graphs. Thus, the proposed UGA module, which unifies the four types of graph augmentations, has yet to guarantee the semantic invariance of augmentation. Fortunately, the learnable characteristic of UGA prevents the semantic shift from random operations in previous GAs. Thus, the invariance can be enhanced via the consistency constraints.", "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": "", "extra_scores": {}}, {"review_id": "RzaNwbjtb5", "reviewer": "Reviewer_BtAD", "summary": "The paper reconsiders the formulation of graph augmentations in graph contrastive learning, introducing a novel perspective on GA through message passing. The proposed UGA framework interprets graph augmentations as mechanisms for aggregation and propagation between nodes, highlighting the significance of local aggregation and propagation within GA. The effectiveness of the proposed GOUDA framework is demonstrated in experimental evaluations.", "questions": "- Can the proposed GOUDA, especially the Graph Augmentation Vectors (GAVs), be integrated with other Graph Contrastive Learning (GCL) methods?\n- How to assess the contribution of the proposed GOUDA framework to Graph Contrastive Learning (GCL)?", "limitations": "The paper requires interpretability and should clarify the contribution to GCL.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- The formulation of GA from the perspective of message passing is intriguing. Construing GA as aggregation and propagation among neighbors adds significant flexibility.\n- The proposed GOUDA framework demonstrates effectiveness and robustness.\n- The paper exhibits superiority across various graph-based tasks, including node classification, node clustering, and graph classification. These results indicate that GOUDA is not limited to specific tasks.\n- The computational complexity is significantly reduced over a wide range.\n- Well-written.", "weaknesses": "- The paper lacks presentation on the interpretability of learned graph augmentation vectors. Given that graph augmentation can occur at nodes, edges, attributes, and sub-graphs, an explanation of how these learned vectors are interpreted is necessary.\n- The paper should include a comparison of time consumption during experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "***Q1. The paper lacks presentation on the interpretability of learned graph augmentation vectors.*** \n\nR1. To provide interpretation for Graph Augmentation (GA), we would first introduce the interpretable explanations for GNNs (i.e., graph encoders) on graphs [1]. Within the encoder-relevant computation graph, i.e., the k-hop subgraph, a subgraph that is informative and most influential on the label is specified as an explanation. For a given node, the computation graph corresponds to its $k$-hop neighborhood; for a given graph, it represents the entire graph. Based on this introduction, GAs can be interpreted as techniques that seek to preserve the information-rich subgraphs. Our GA method, which interpolates a batch of Augmentation-Centered (AC) vectors into the input graph to emulate the GAs' effect, is proposed based on an observation: GA is equivalent to modifying the node attributes within the computation graphs of nodes, that is, local attribute perturbation. During the weight optimization guided by an error metric, these AC vectors adaptively capture task-related perturbation information from the computation graphs of nodes. Therefore, the learned AC vectors can be interpreted as the representations of subgraphs in the computation graph of nodes.\n\n[1] GNNExplainer: Generating Explanations for Graph Neural Networks. NeurIPS 2019\n\n\n---\n\n***Q2. The paper should include a comparison of time consumption during experiments.***\n\nR2. We understand your concerns about the complexity of the proposed framework. We have conducted a comprehensive comparison of the running time consumption of GCLs, as shown in Figure 3 of our manuscript. The accuracy and the running time for each training epoch are provided in the following table for your review. \n\n| Accuracy(%) / Time(s) | IMDB-BINARY  | IMDB-MULTI |\n|:--------| :---------:|:--------:|\n| Infograph | 73.03 / 0.82 | 49.69 / 0.89 |\n| GraphCL | 71.14 / 0.49 | 48.58 / 0.56 |\n| JOAO | 71.60 / 1.88 | 49.20 / 1.79 |\n| AD-GCL | 71.49 / 1.31 | 50.36 / 1.44 |\n| MVGRL | 74.20 / 1.16 | 51.20 / 1.02 |\n| GOUDA-IF (Ours) | 75.22 / 0.41 | 52.43 / 0.47 |\n| GOUDA-BT (Ours) | 76.80 / 0.46 | 53.05 / 0.55 |\n\nIt is evident from the table that GOUDA not only outperforms the baselines but also consumes less time per epoch, demonstrating that GOUDA is an effective yet lightweight framework. The detailed analysis has been presented in Section 4.1 of our submitted manuscript.  \n\n---\n\n***Q3. Can the proposed GOUDA, especially the Graph Augmentation Vectors (GAVs), be integrated with other Graph Contrastive Learning (GCL) methods?***\n    \nR3. Of course. As a general framework, GOUDA possesses high compatibility with most GCLs, enabling integration through slight modifications of the graph encoder or the loss function. In our submitted manuscript, GOUDA is implemented as two models: GOUDA-IF, which utilizes InfoNCE loss, and GOUDA-BT, which employs BarlowTwins loss. Extensive experiments (such as graph classification in the table of R2) on various datasets and tasks demonstrate the outstanding performances of GOUDA-IF and GOUDA-BT, highlighting the broad compatibility and effectiveness of the framework GOUDA.  \n\n---\n\n***Q4. How to assess the contribution of the proposed GOUDA framework to Graph Contrastive Learning (GCL)?***\n\nR4. We would like to illustrate the contribution of the proposed framework GOUDA to GCL from the following aspects:\n1. **A novel perspective of graph augmentations**. GOUDA is designed with a thorough analysis of the mechanisms of existing Graph Augmentations (GAs) in GCLs. We provide a unified interpretation of these mechanisms from a message-passing perspective, offering new insights into the GCL field.\n2. **A general graph augmentation module**. GOUDA presents a lightweight yet effective GA module, i.e., UGA, that achieves a theoretical unification of diverse GAs, providing an innovative GA strategy to GCLs.\n3. **New SOTA**. The implemented models, GOUDA-IF and GOUDA-BT, have achieved a new state-of-the-art performance on many tasks, including node/graph classification.", "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": "", "extra_scores": {}}, {"review_id": "OBIzgAFMfP", "reviewer": "Reviewer_9GrB", "summary": "This paper explores the characteristics of local attribute modification in current graph contrastive learning methods. It then integrates diverse augmentation strategies with attribute learning into a unified framework. This unified approach introduces a novel and straightforward graph contrastive learning framework that establishes consistency between embeddings and ensures diversity through augmentation. Specifically, diversity is enforced using the HSIC term. The proposed framework offers two main advantages: 1) high efficiency and 2) universally learnable augmentation. Its effectiveness is validated across graph-level and node-level tasks, demonstrating its superiority.", "questions": "See above.", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The exploration of graph contrastive learning mechanisms from a spatial perspective is insightful.\n\n- The unified augmentation proposed and the subsequent framework are both straightforward and efficient.\n\n- The use of shared AC and HSIC is technically robust.\n\n- The experimental evaluations provide convincing evidence.", "weaknesses": "- The symbols $\\gets$ used in many equations, such as Eq. (4), should be changed to $\\to$ for convenience.\n\n- Some experiments require further explanation. It's unclear why the proposed framework demonstrates robustness to topology and attribute noises.\n\n- Some hyper-parameters remain unverified. It's uncertain whether the parameter $\\varepsilon$ in Eq. (7) significantly affects performance.\n\n- As far as I know, the HSIC term is computationally intensive. Does this affect efficiency?\n\n- Descriptions from Lines 143 to 153 are difficult to understand.\n\n- Reference [33] is based on adversarial training rather than adversarial attack.\n\n- Some commas are missing after equations, for instance, in Eq. (9).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "***Q1. The symbols $\\leftarrow$ used in many equations, such as Eq. (4), should be changed to $\\rightarrow$ for convenience.***\n\nR1. Following your advice, we will revise the equations to replace the symbols $\\leftarrow$ with the symbols $\\rightarrow$ to enhance readability. \n\n---\n\n***Q2. It's unclear why the proposed framework demonstrates robustness to topology and attribute noises.*** \n\nR2. Before we explain the robustness advantages of our proposed framework that employs learnable Graph Augmentation (GA) over the baseline models that utilize static and random GAs, we first describe the impact of noise attacks on graphs. Specifically, noise attacks can potentially destroy the semantic subgraphs crucial for predictions, thereby inducing distortions in the learned representations. However, random GAs struggle to preserve the information-rich subgraphs and may further destroy them, exacerbating semantic bias. In contrast, the proposed learnable GAs, trained with a relevant proxy task like contrastive loss, can preserve such subgraphs and, hence, can mitigate semantic bias. \n\n---\n\n***Q3. It's uncertain whether the parameter $\\varepsilon$ in Eq. (7) significantly affects performance.*** \n\nR3. According to your suggestion, we verify the impact of the hyper-parameter $\\varepsilon$ on model performance. $\\varepsilon$ stands for the threshold to suppress the elements in $B$ to zeros. Thus, to eliminate bias due to network size,  $\\varepsilon$ is not freely tuned. Instead, it is set as the output of the selection function, i.e., $\\varepsilon = \\text{selection}(B, s)$, which estimates this threshold. $B$ represents the matrix of propagation weights from AC vectors to nodes, and $s$ denotes the presence of the largest elements retained. $s$ is chosen from the set {0.2, 0.4, 0.6, 0.8} in the experiments. Thus, the impact of $s$ on the performance is shown in the following table. It can be observed that $s$ does not significantly affect the model performance. \n\n| GOUDA-IF | 0.2  | 0.4| 0.6 | 0.8 |\n|:--------| :---------:|:--------:|:--------:|:--------:|\n| Cora | 85.29 | 84.71 | 84.19 | 86.11 |\n| CiteSeer | 74.55 | 73.20 | 73.11 | 73.62 |\n| PubMed | 86.96 | 87.25 | 87.55 | 87.05 | \n\n| GOUDA-BT | 0.2  | 0.4| 0.6 | 0.8 |\n|:--------| :---------:|:--------:|:--------:|:--------:|\n| Cora | 85.07 | 84.56 | 85.88 | 85.99 |\n| CiteSeer | 74.34 | 74.47 | 73.98 | 73.41 |\n| PubMed | 87.59 | 86.94 | 86.76 | 87.11 |\n\n---\n\n***Q4. As far as I know, the HSIC term is computationally intensive. Does this affect efficiency?***\n\nR4. There may be some misunderstandings. The HSIC term has a quadratic time complexity of $O(N^2)$ for the number of samples $N$. However, this complexity is mitigated to $O(K^2)$ in the proposed framework since HSIC is applied only to $K$ AC vectors instead of the entire node set. The proposed framework sets $K$ as a small number, which is independent of the size of the graph. Therefore, the employment of the HSIC term does NOT cause high computation in the proposed framework. \n\n---\n\n***Q5. Descriptions from Lines 143 to 153 are difficult to understand.***\n\nR5. We have carefully reviewed the content and have reorganized the passage for better clarity and comprehension. The passage now presents as follows.\n\n(1) Edge augmentation is to add or remove the augmented edges, which corresponds to inserting or dropping the nodes connected by these edges in the neighborhood of the impacted nodes. The shown edge removal will lead to dropping certain 2-hop neighbors (nodes 1, 4, 7, and 8) of node 0 during the aggregation phase.\n\n(2) Attribute augmentation is to replace the attributes of the impacted nodes with the altered attributes, which affects all nodes connected to them. The shown attribute augmentation can be seen as modifying the attributes of the augmented neighbors (nodes 1, 3, 4, 5, 6, 7, and 8) of node 0 during the aggregation phase.\n\n(3) Subgraph augmentation is to modify the specific subsets of the input graph (including its edges and attributes), which also can be seen as the perturbation in the neighborhoods of impacted nodes. The shown subgraph augmentation will lead to the removal of nodes 2, 4, 6, and 8 from the 2-hop neighborhood of node 0 during the aggregation phase.  Furthermore, node augmentation represents a specific case of subgraph augmentations, with the subset limited to a single node, thus rendering the aforementioned conclusion applicable to it.\n\n---\n\n***Q6. Reference [33] is based on adversarial training rather than adversarial attack.***\n\nR6. Thank you for the meticulous correction. We will correct the methodology of Reference [33] to adversarial training. \n\n---\n\n***Q7. Some commas are missing after equations, for instance, in Eq. (9).***\n\nR7. Thank you for your attention to detail. We will carefully check and comprehensively polish the manuscript to make sure that all formulas are followed by the correct punctuation.", "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": "", "extra_scores": {}}, {"review_id": "oAhpAdxdUX", "reviewer": "Reviewer_sGNH", "summary": "This paper investigates the generality of graph augmentations across various types of graphs and tasks. Firstly, the paper presents a new interpretation that unifies the various graph augmentations into local attribute modifications of each node from a basic message-passing perspective. Then, the paper develops a novel graph augmentation module that alters node attributes to simulate the augmentation effects. Utilizing this module, the paper presents a novel framework for graph contrastive learning, where the balance between consistency and diversity across different augmented views is carefully considered. Finally, it provides a theoretical understanding of the generality of the proposed framework. Extensive evaluations demonstrate its superior performance on diverse datasets and tasks.", "questions": "Please refer to Weaknesses.", "limitations": "N/A", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) This paper is well-organized and well-written. \n2) The motivation of unifying graph augmentations from a message-passing view is interesting. \n3) The proposed framework is simple and efficient with solid theoretical guarantee.\n4) Experiments across various types of graphs and tasks demonstrate the superior efficacy and efficiency of the proposed method in comparison to existing works.", "weaknesses": "1) There are a few typos and grammar mistakes in the paper that need fixing. \n2) The theoretical analysis requires intuitive explanations. While the authors offer the proof of generality, they should elucidate how the theorem relates to the superior performance. \n3) The concepts of consistency and diversity deserve a more comprehensive explanation. Additionally, how do the definitions of consistency and diversity across augmentations in self-supervised learning scenarios differ from those in semi-supervised learning scenarios? \n4) The connection between the number of AC vectors and model performance is not clear.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "***Q1. There are a few typos and grammar mistakes in the paper that need fixing.***\n\nR1. Thanks for your thoughtful reminder. We will polish our manuscript to elevate the quality and clarity. \n\n---\n\n***Q2. While the authors offer the proof of generality, they should elucidate how the theorem relates to the superior performance.***\n\nR2. An intuitive explanation is that the generality improves the flexibility of the augmentation, which is the need for diverse graph tasks. Graphs and corresponding tasks possess diverse characteristics and, hence, need different augmentation strategies to meet their diverse and complicated requirements. However, existing graph augmentations, no matter whether heuristics or learnable ones are limited to selecting from discrete candidate sets, e.g., node or edge dropping and attribute masking; thus, some flexible and continuous augmentations can NOT be achievable to satisfy these diverse needs. Fortunately, the proposed GA module is endowed with theoretical versatility, enabling it to be equivalent to any flexible graph augmentations. Therefore, by equipping with this versatile module, the proposed model can be flexibly tailored to meet the diverse GA demands across different tasks. The versatility and flexibility have propelled our framework to achieve outstanding performance across various datasets and tasks, outperforming existing GCL baselines. \n\n--- \n\n***Q3. The concepts of consistency and diversity deserve a more comprehensive explanation.***\n\nR3. **Consistency** means that the augmented graph maintains the underlying structure and key features of the original graph. Therefore, GAs should minimally impact the similarity between the representations from different augmented graphs to preserve the intrinsic semantic integrity of samples. In contrast, **diversity** indicates that the augmented graphs originate from diverse distributions. Thus, another objective of GAs is to minimize the overlap between augmented graphs, ensuring the model does not become overly fixated on the specific features of a single distribution. \n\n---\n\n***Q4.  How do the definitions of consistency and diversity across augmentations in self-supervised learning scenarios differ from those in semi-supervised learning scenarios?***\n\nR4. The distinction in the concepts of consistency and diversity between self-supervised and semi-supervised learning scenarios primarily stems from the availability of supervision signals. \n\n1. **Semi-supervised learning** \n\n- Consistency: It is often defined as the extent to which augmented graphs align with the inherent patterns of the labeled data.\n\n- Diversity: It is often defined as the difference in distribution between the augmented and input graphs.\n\n1. **Self-supervised learning**\n\n- Consistency: It is often defined as the extent to which various augmented graphs preserve the essential characteristics of the input graph. \n\n- Diversity: It is often defined as the distributional differences among the various augmented graphs. \n\n---\n\n***Q5. The connection between the number of AC vectors and model performance.***\n\nR5. We recognize your concerns about the selection of the $k$, which is a key hyperparameter in the proposed GOUDA. The proposed framework sets $k$ as a small number, which is independent of the size of the graph. The submitted manuscript has presented an experimental assessment of the impact of varying $k$ on model performance, as shown in Figure 7, where $k$ is selected from the set {1, 5, 10, 20}. Our observations indicate that GOUDA is relatively insensitive to the hyperparameter $k$ as explained in Section 4.2. Therefore, one need not be overly concerned with the precise value of $k$ for GOUDA’s robustness to changes in $k$.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper addresses potential limitations in existing Graph Contrastive Learning (GCL) frameworks, specifically the issues of specificity, complexity, and incompleteness of Graph Augmentation (GA) techniques. The authors introduce UGA, a method with theoretical guarantees, alongside GOUDA, a framework that can be integrated with various contrastive losses. Experimental results demonstrate the effectiveness of GOUDA in enhancing GCL performance.

The paper has received predominantly positive feedback both before and after the rebuttal period, with final scores of (8, 7, 7, 5). Please carefully consider the questions and concerns raised by the reviewers, particularly those from reviewer i3ih, when the authors preparing the final version of the paper, e.g., some implementation details and more comparisons.
Decision: Accept (poster)