Unified Graph Augmentations for Generalized Contrastive Learning on Graphs

Q1. There are a few typos and grammar mistakes in the paper that need fixing.

R1. Thanks for your thoughtful reminder. We will polish our manuscript to elevate the quality and clarity.

Q2. While the authors offer the proof of generality, they should elucidate how the theorem relates to the superior performance.

R2. 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.

Q3. The concepts of consistency and diversity deserve a more comprehensive explanation.

R3. 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.

Q4. How do the definitions of consistency and diversity across augmentations in self-supervised learning scenarios differ from those in semi-supervised learning scenarios?

R4. 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.

1. Semi-supervised learning

• Consistency: It is often defined as the extent to which augmented graphs align with the inherent patterns of the labeled data.

• Diversity: It is often defined as the difference in distribution between the augmented and input graphs.

1. Self-supervised learning

• Consistency: It is often defined as the extent to which various augmented graphs preserve the essential characteristics of the input graph.

• Diversity: It is often defined as the distributional differences among the various augmented graphs.

Q5. The connection between the number of AC vectors and model performance.

R5. 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$.

Thank you for the authors' detailed response. I am satisfied with the authors' response and revised manuscript, so I would like to increase my score from 7 to 8.

Q1. The symbols $\leftarrow$ used in many equations, such as Eq. (4), should be changed to $\rightarrow$ for convenience.

R1. Following your advice, we will revise the equations to replace the symbols $\leftarrow$ with the symbols $\rightarrow$ to enhance readability.

Q2. It's unclear why the proposed framework demonstrates robustness to topology and attribute noises.

R2. 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.

Q3. It's uncertain whether the parameter $\varepsilon$ in Eq. (7) significantly affects performance.

R3. 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.

Q4. As far as I know, the HSIC term is computationally intensive. Does this affect efficiency?

R4. 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.

Q5. Descriptions from Lines 143 to 153 are difficult to understand.

R5. We have carefully reviewed the content and have reorganized the passage for better clarity and comprehension. The passage now presents as follows.

(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.

(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.

(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.

Q6. Reference [33] is based on adversarial training rather than adversarial attack.

R6. Thank you for the meticulous correction. We will correct the methodology of Reference [33] to adversarial training.

Q7. Some commas are missing after equations, for instance, in Eq. (9).

R7. 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.

Q1. The paper lacks presentation on the interpretability of learned graph augmentation vectors.

R1. 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.

[1] GNNExplainer: Generating Explanations for Graph Neural Networks. NeurIPS 2019

Q2. The paper should include a comparison of time consumption during experiments.

R2. 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.

It 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.

Q3. Can the proposed GOUDA, especially the Graph Augmentation Vectors (GAVs), be integrated with other Graph Contrastive Learning (GCL) methods?

R3. 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.

Q4. How to assess the contribution of the proposed GOUDA framework to Graph Contrastive Learning (GCL)?

R4. We would like to illustrate the contribution of the proposed framework GOUDA to GCL from the following aspects:

1. 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.
2. 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.
3. 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.

Q1. The paper could provide more intuitive explanations and step-by-step derivations to enhance understanding.

R1. 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.

Q2. While authors have compared with many GCL methods, the comparison with GA techniques like simple node augmentation is missing.

R2. 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.

Figure 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.

It 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.

[1] Graph Contrastive Learning with Augmentations. NeurIPS 2020

Q3. How to interpolate the learned AC vectors?

R3. 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.

Q4. How is k selected in line 181?

R4. 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$.

Q5. Graph augmentation is based on the assumption that the augmentation does not change the original class label, how does UGA guarantee this?

R5. 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.