Bootstrapping Informative Graph Augmentation via A Meta Learning Approach

1 Introduction

Recently, there has been a surge of interest in learning a graph representation via self-supervised Graph Neural Network (GNN) approaches. GNNs, inheriting the powerful representation capability of neural networks, emerged as benchmark approaches over many graph representation learning tasks. Early works mostly require task-dependent labels to learn a graph representation. However, annotating graphs is a rather challenging task compared to labeling common modalities of data, especially in specialized domains. Therefore, recent research efforts are dedicated to developing selfsupervised graph representation learning methods, which can eliminate the dependency of the labels [Hu et al., 2020b].

∗Contributed equally to this work, in no particular order.

†Corresponding author

Graph contrastive learning (GCL), one of the most popular self-supervised methods in graph representation learning, is proposed based on GNNs and contrastive learning. Under the learning paradigm of contrastive learning, GCL generates augmented graphs by adopting graph augmentation [Hassani and Khasahmadi, 2020]. After graph encoding, the augmented and original features of the same graph are treated as positives, and the features of different graphs are treated as negatives. The object of GCL is to learn a good graph representation by pulling the positives close and pushing the negatives apart. However, most of the graph augmentation approaches are non-learnable, which causes two issues: 1) the augmentation is excessively weak, e.g., the augmented graph is indistinguishable from the original graph, and the contrastive learning model can hardly mine consistent knowledge from them; 2) the augmentation introduces overmuch noise, and the augmented graph is even more similar to other graphs. The mentioned issues weaken GCL's ability to learn a discriminative representation. Therefore, we motivate our method to directly learn a graph augmentation, which can assist GCL in generating a good graph representation.

We aim to learn a "good" graph representation that can have impressive performance on downstream tasks, but what is an exact "good" representation? From [Grill et al., 2020], we notice that, at the instance-level, a good representation naturally has uniformity, e.g., features of different samples are scattered throughout the hidden space instead of collapsing to a point. However, such constraint does not consider the representation's collapse at the feature-level. For instance, the learned representation has 256 dimensions, but most of them have few differences, which implies that much information learned by the representation is redundant [Zbontar et al., 2021]. Such redundant information may lead to limited informativeness of the representation and degenerate the representation to model truly discriminative information. Therefore, we motivate our method to learn a "good" representation with uniformity at the instance-level and informativeness at the feature-level.

To this end, we propose MEta Graph Augmentation (MEGA) to guide the encoder to learn a discriminative and informative graph representation. For training the encoder, we follow the common setting of contrastive learning [Chen et al., 2020]. The well self-supervised contrastive learning approach leads the features to be scattered in the hidden space. However, in practice, the sufficient self-supervision of the contrastive learning approach demands hard (informative at the instance-level) features of positive and negative samples, e.g., positive features that are relatively far apart and negative features that are relatively close in the hidden space. For instance, [Chen et al., 2020] leverages large batch and memory bank to include more hard features, [Chuang et al., 2020] explore to emphasize hard features in training. At the instance-level, our motivation is to straightforwardly generate hard graph features by a learnable graph augmenter (LGA), which uses the encoder's performance in one iteration to generate hard features for the next iteration by updating the graph augmentation. Note that the objective of LGA is not to promote convergence of contrastive loss. On the contrary, we expect LGA to generate an augmented graph that can increase the difficulty of the self-supervision problem (i.e., contrasting). Contrastive learning aims to put the original and augmented features of a graph together and push the features of different graphs away, and LGA aims to degenerate such a process. Therefore, the LGA augmented graph feature must be hard for contrastive learning. To ensure the informativeness of the learned representation at the feature-level, we propose to train LGA to augment the graph so that it can improve the encoder to generate a representation with informativeness at the feature-level. As shown in Figure 1, LGA is like a teacher that shows different hard and informative examples (augmented graphs) to the encoder, and the contrastive loss leads the encoder to learn discriminative knowledge from them.

The reason why we take a meta-learning approach to update LGA is as follows: the learning paradigm of metalearning ensures that the optimization objective of LGA is improving the encoder to learn representations with uniformity at the instance-level and informativeness at the featurelevel from graphs. However, a regular learning paradigm, e.g., directly optimizing LGA by the loss of measuring the uniformity and informativeness of features in hidden space, can only ensure that the features learned from the augmented graph are modified. However, the features learned from the original graph could be collapsed or non-informative. Concretely, the meta-learning paradigm ensures that the encoder learns the knowledge to generate good representations with uniformity at the instance-level and informativeness at the feature-level.

Contributions. The takeaways of this paper are as follows:

• We propose a learnable approach to generate informative graph augmentation, called meta graph augmentation, which boosts the performance of graph contrastive learning.
• We propose an auxiliary meta-learning approach to train the learnable graph augmenter, which guides the encoder to learn a representation with uniformity at the instancelevel and informativeness at the feature-level.
• We conduct experiments to compare our method with state-of-the-art graph self-supervised learning approaches on benchmark datasets, and the results prove the superiority of our method.

2 RelatedWorks

In this section, we review some representative works on graph neural networks, graph contrastive learning, and metalearning, which are related to this article.

Graph Neural Networks (GNN). GNN can learn the lowdimensional representations of graphs by aggregating neighborhood information. These representations can then be applied to various kinds of downstream tasks. Like other neural network structures, GNNs developed many variants. Graph Convolution Networks (GCNs) [Kipf and Welling, 2016], as an extension of the convolutional neural network on graphstructured data, use convolution operation to transform and aggregate features from a node's graph neighborhood. [Xu et al., 2018] shows that GNNs are at most as powerful as the Weisfeiler-Lehman test in distinguishing graph structures. Based on this idea, [Xu et al., 2018] proposed Graph Isomorphism Networks (GINs). Graph Attention Networks (GATs) [Veliˇckovi´c et al., 2017] introduces attention mechanisms into graph learning.

Contrastive learning. Contrastive Learning is a kind of self-supervised learning approach that measures the loss in latent space by contrasting features in hidden space. CMC [Tian et al., 2020] uses multi-view data to acquire features for contrasting. In computer vision, many works based on contrastive learning have achieved outstanding results in different kinds of tasks [Chen et al., 2020] [Zbontar et al., 2021].

As in graph learning, contrastive learning also has many applications. For instance, DGI [Veliˇckovi´c et al., 2018] learns node representations through contrasting node and graph embeddings. [Hassani and Khasahmadi, 2020] learns node-level and graph-level representations by contrasting the different structures of a graph.

Meta learning. The objective of meta-learning is to learn the learning algorithm automatically. Early works [Schmidhuber, 2014] aim to guide the model (e.g., neural network) to learn prior knowledge about how to learn new knowledge, so that the model can efficiently study new information. Recently, researchers explored using meta-learning to find optimal hyper-parameters and appropriately initialize a neural network for few-shot learning [Finn et al., 2017].

3 Methods

In this section, we introduce the proposed MEta Graph Augmentation (MEGA). The architecture of MEGA is depicted in Figure 2. MEGA proposes to learn informative graph augmentation by a meta-learning approach. Guided by the augmented graph, the GNN encoder can mine hidden discriminative knowledge from the original graph.

3.1 Preliminary

We recap necessary preliminary concepts and notations for further exposition. In this paper, we consider attributed graphs G = (V ,E) where V is a node set and E is the corresponding edge set. For G, {Xv ∈ RV |v ∈ V } denotes the node attributes.

Learning graph representations. Given a graph dataset G including Gi, where i ∈ �1,N�. Our objective is to learn an encoder f(·) : G → RD , where f(Gi) is a representation that contains discriminative information of Gi and can be further used in downstream task. We assume Gi as a random variable that is sampled i.i.d from distribution P (G) defined over G. To learn such discriminative representation f(Gi), we adopt GNN as the encoder and then perform self-supervised contrastive learning in hidden space.

Graph Neural Networks. In this paper, we focus on using GNN, message passing GNN in particular, as the encoder f(·). For graph Gi = (Vi,Ei), we denote Hv as the representation vector, for each node v ∈ Vi. The k-th layer GNN can be formulated as:

where N(v) denotes the neighbors of node v, H(k) is the representation vector of the node v at layer k, and when k = 0, H(0) is initialized with the input node features, which is extracted fromX. combine and aggregate are functions with learnable parameters. After K rounds of massage passing, a readout function will pool the node representations to obtain the graph representation hi for Gi:

Contrastive learning. We follow the preliminaries of contrastive learning [Tian et al., 2020]: learning an embedding that maximizes agreement between the original and augmented features of the same sample, namely positives, and separates the features of different samples, namely negatives, in latent space. We denote G′i is the augmented graph of Gi. To impose contrastive learning, we feed the inputs Gi and G′i into the encoder f(·) to learn representations hi and h′i , and the representations are further mapped into features zi and z′i by a projection head g(·) [Chen et al., 2020]. The encoder f(·) and projection head g(·) are trained by contrasting the features, and the loss [Oord et al., 2018] is formulated as follows:

where z+ denotes the pair of {z′i , zi}, z- is a set of pairs, i.e., {{z′j , zi}, {z′i , zj}∣∣∣j ∈ �1, N�, j ̸= i}, < · > denotes a discriminating function to measure the similarity of features, and τ is the temperature factor [Chen et al., 2020]. Note that, after training is completed, the projection head g(·) is discarded, and the representations are directly used for downstream tasks.

3.2 Meta Graph Augmentation

Different from benchmark methods that randomly dropping or adding edges to augment a graph [Hassani and Khasahmadi, 2020] [Wan et al., 2020], we motivate our method to impose graph augmentation in an learnable manner [Suresh et al., 2021]. We rethink the learning paradigm of contrastive learning and find that such an approach relies heavily on hard and informative features in training. Therefore, to boost the performance on downstream tasks of the learned representations, we propose to use a trick of meta-learning to generate informative graph augmentation, which is to guide the encoder to mine discriminative knowledge from graphs.

Learnable Graph Augmentation

As the architecture shown in Figure 2, we propose a learnable approach to augment graph. In detail, suppose A is the adjacency matrix of Gi where the initial weights of the connected nodes are set to 1 and others are valued by 0. ˜ A = A+ I, where I denotes the self-connection of each node e ∈ E. We use a neural network a(·), as the LGA (see Appendix for the implementation), to generate the augmented graph G′i from the original graphGi, where ˜ A′i is the adjacency matrix with self-connections I of a graph G′i . Gi and G′i are then encoded into features zi and z′i by the encoder f(·) and projection head g(·).

Auxiliary Meta Learning

In contrastive learning, we need hard and informative features to learn discriminative representations. To this end, we build an LGA and train it by a meta-learning approach. In training, we first fix LGA aσ(·) and train the encoder fϕ(·) and the projection head gφ(·) by back-propagating Lcontrast, where σ, ϕ, and φ denote the network parameters of a(·), f(·), and g(·), respectively. Then, fϕ(·) and gφ(·) are fixed, and aσ(·) is trained by computing its gradients with respect to the performance of fϕ(·) and gφ(·), and the meta-learning updating objective is as follows:

where g˚ φ(f˚ ϕ (G)) denotes a set of the features extracted from original graphs, g˚ φ(f˚ ϕ (aσ(G))) denotes a set that includes the features of augmented graphs, and aσ(G) denotes G′ . ˚ ϕ and ˚ φ represent the corresponding parameters of the encoder and projection head, which are updated with one gradient back-propagation using the contrastive loss defined in Equation 3:

where ℓ is the learning rate shared between ϕ and φ. The idea behind the meta updating objective is that we perform the second-derivative trick [Liu et al., 2019] to train aσ(·). Specifically, a derivative over the derivative (i.e., a Hessian matrix) of {ϕ, φ} is used to update σ. We compute the derivative with respect to σ by using a retained computational graph of {ϕ, φ}. Then, σ is updated by

where ℓ′ represents the learning rate of σ, and ̂ G′ is the augmented graphs with stop-gradient, which is defined as ̂ G′ = aσ(G).detach(). LMEGA is to train aσ(·) to generate hard and informative augmented graphs defined as follows:

where tr(·) denotes the matrix trace function, which is defined as tr(M) = ∑i Mii, and de(·) is a matrix calculation function defined as de(M) = ∑i ∑j̸=i Mij. | · |2 presents a matrix element-wise square function defined as |M|2 = M × M by Hadamard product, and 1 presents an identity matrix. λ is the coefficient that controls the balance between two terms of LMEGA. Intuitively, the instance term aims to lead MEGA to generate instance-level challenging examples for self-supervised learning. Inspired by [Zbontar et al., 2021], we design the feature term to promote the model to learn dimensionally non-redundant representations, respectively. Concretely, minimizing the proposed LMEGA by using the second-derivative technique can guide aσ(·) to generate hard and informative augmented graphs. C denotes the cross-correlation matrix computed between the features of the original graphs and augmented graphs in a batch, as follows:

where i, j ∈ �1,N� in a batch N of graphs. D is the crosscorrelation matrix computed between the multi-dimensional features of the original graphs and the corresponding augmented graphs along the batch, which is defined as:

where i ∈ �1,N� indexes batch graphs and p, q ∈ �1,N D � index the feature dimension of the original graph and the corresponding augmented graph, and N D denotes the number of feature dimension. C, D aim to train aσ(·) to generate hard and informative augmented graphs, respectively. Concretely, the objective of auxiliary meta-learning is to enable LGA to learn augmented graphs that are hard and informative for the encoder, thereby improving the encoder's learning process for the next iteration.

4 Experiments

In this section, we demonstrate the effectiveness of MEGA on various benchmark datasets. Our experiments were conducted in an unsupervised learning setting.

4.1 Comparison with State-of-the-art Methods

Datasets. We evaluate our method on twelve benchmark datasets in two major categories: 1) Social Networks: RDTM5K, IMDB-B, IMDB-M from TU Dataset [Morris et al., ]. 2) Molecules: PROTEINS, MUTAG, COLLAB and DD from TU Dataset [Morris et al., ] and molesol, mollipo, molbbbp, moltox21 and molsider from Open Graph Benchmark (OGB) [Hu et al., 2020a].

Experiment settings. We compared MEGA with four unsupervised/self-supervised learning baselines, which include randomly initialized untrained GIN (GIN RIU) [Xu et al., 2018], InfoGraph [Sun et al., 2020], GraphCL [You et al., 2020] and AD-GCL [Suresh et al., 2021]. Experiment results of InfoGraph [Sun et al., 2020] and GraphCL [You et al., 2020] show that they generally outperform graph kernel and network embedding methods including [Kriege et al., 2020], [Grover and Leskovec, 2016], and [Adhikari et al., 2018]. As discussed in the method section, the instance-level constrains and feature-level constraints of LMEGA are balanced by parameter λ. To study the effects of these constraints, we set λ = 0 for the ablation study, termed MEGA-IL. We followed the experimental protocol of AD-GCL, including the train/validation/test splits. The average classification accuracy with standard deviation on the test results over the last ten runs of training is reported. For a fair comparison, we adopted GIN as the encoder as other baselines do. We adopt the Adam optimizer with a learning rate of 10-4 for learnable graph augmentation and a learning rate of 10-3 for graph encoding. We use 50 training epochs on all datasets. All methods adopt a downstream linear classifier or regressor with the same hyper-parameters.

Results. The results are reported in Table 1 and 2. The results show that MEGA achieves the best results compared with baselines across benchmark datasets. We attribute such performance to MEGA's abilities to generate both hard and informative augmented graph features. The results show that MEGA outperforms MEGA-IL across most datasets, which proves that the feature-level constraints do improve the net-

0.001

0.01

0.1

λ

(a) MUTAG

0.001

0.01

0.1

λ

(b) PROTEINS

0.001

0.01

0.1

λ

(c) IMDB-B

Figure 3: Results of MEGA's performance with a range of factor λ. We perform MEGA on three benchmark datasets: MUTAG, PROTEINS,

and IMDB-B. The abscissa axis represents the value of λ, and the ordinate axis represents the accuracies.

work to learn informative representations. MEGA-IL still performs better than most of the baselines that adopt the same encoder and contrastive learning pattern, which means that the instance-level constrains of LMEGA work well.

4.2 Evaluation of Feature-level Constrains

For further evaluation of feature-level constraints, we change the value of λ and observe how the performance changes. We adopt three different datasets, including two molecule datasets and one social network dataset.

The results are reported in Figure 3. The performance changes as the factor λ changes. When λ takes 0.1, the performance is optimal among all tasks. The results prove that feature-level constraints can enhance the discrimination of features to a certain extent. The feature-level constraints ensure that the generated augmented graph correlates with the original graph, preventing LGA from learning outrageous graph augmentation. However, if we overly increase the impact of feature-level constraints, the generation of hard augmented graph features could be interfered.

4.3 Analyze on Representations

To better understand the quality of the representations learned by MEGA, we visualize the output graph features. For comparison, we conducted experiments on four different networks: (1) UNTRAINED, a randomly initialized GIN encoder without training. (2) CCL, a conventional graph contrastive learning network without our proposed LGA. (3) MEGA-IL, MEGA without feature-level constraints. (4) MEGA.

The results are shown in Figure 4. We intuitively observe the representations of each graph and find that MEGA and MEGA-IL output more "colorful" results than UNTRAINED and CCL, which indicates that their output is more informative. For the output of MEGA, there are many vertical lines of different colors, which means that the difference between the dimensions of the feature is significant.

5 Conclusions

This paper proposed a novel meta graph augmentation to boost the representation ability of graph contrastive learning. We apply secondary derivative technique to update a learnable graph augmenter, which is to generate hard and informative augmented graph for contrastive learning. This way, we can yield a representation with uniformity at the instancelevel and informativeness at the feature-level.

0.0001

1

10

0.0001

1

10

0.0001

1

10

Acknowledgements

The authors thank all the anonymous reviewers. This work is supported by the Strategic Priority Research Program of the Chinese Academy of Sciences, Grant No. XDA19020500.