Ada-MIP: Adaptive Self-supervised Graph Representation Learning via Mutual Information and Proximity Optimization

Graph kernels refer to a class of methods that compare pairs of graph data points using particular similarity measures. The researches on graph kernels could be traced back to 2003 [Gärtner et al. 2003; Kashima et al. 2003]. Then several kernels specifically designed for graphs have been proposed. The Shortest-Path (SP) kernel [Borgwardt and Kriegel 2005] compared the attributes and lengths of the shortest paths between all pairs of vertices in two graphs. The Graphlet kernel [Shervashidze et al. 2009] was based on counting occurrences of subgraph patterns of a fixed size. Shervashidze et al. [2011] introduced the Weisfeiler-Lehman subtree kernel for graphs with discrete labels based on the 1-dimensional Weisfeiler-Lehman (1-WL). The Sub-graph Matching kernel [Kriege and Mutzel 2012] was computed by considering all bijections between all sub-graphs on at most \(k\) vertices. The Pyramid Match (PM) kernel [Nikolentzos et al. 2017] represented each graph as a set of vectors corresponding to the embeddings of its vertices and employs the Earth Mover’s Distance metric for similarity computation. The Multiscale Laplacian Graph (MLG) kernel [Kondor and Pan 2016] was able to capture the graph structure at multiple scales, i.e., neighborhoods around vertices of increasing depth by using ideas from spectral graph theory.

In recent years, GCL has emerged as a promising method for self-supervised graph representation learning. Deep Graph Infomax (DGI) [Velickovic et al. 2019] and InfoGraph [Sun et al. 2019] followed the Infomax Principle [Linsker 1988] to learn node-level/graph-level representations by maximizing the mutual information (MI) between global and local representations. Graph Contrastive Learning (GraphCL) [You et al. 2020] applied hand-pick graph augmentations to incorporate various priors and learned to maximize the agreement of graph augmentations originated from the same graph. Multi-View Graph Representation Learning (MVGRL) [Hassani and Khasahmadi 2020] augmented graphs via graph diffusion and randomly sample corresponding sub-graphs from original and augmented graphs as two views. Then it crossly contrasted the local and global features of the two views. GCA [Zhu et al. 2021b] used heuristics based on the network centrality to adaptively sample nodes (features) to be preserved. GMI [Peng et al. 2020] aims at maximizing the MI between the input, i.e., node features and topological structure, and outputs embeddings of the GNN encoder. Joint Augmentation Optimization (JOAO) [You et al. 2021] extended the GraphCL by employing a bi-level min-max optimization to select the combination of augmentations. Adversarial Graph Contrastive Learning (AD-GCL) [Suresh et al. 2021] employed an adversarial training strategy to learn a GNN-based augmenter and a GNN encoder, which aim at capturing the minimal sufficient information to distinguish graphs. AutoGCL [Yin et al. 2021] used a set of learnable graph view generators each of which learned a probability distribution of augmented graphs in the contrastive learning procedure. SimGRACE [Xia et al. 2022] augmented input graphs by permuting the parameters of the graph encoder, thus not requiring manual picked graph augmentations. Despite that existing works have made some attempts to automatic augmentation in graph contrastive learning, they do not consider the injectivity of employed augmenter or the inter-graph proximity information. Instead, our Ada-MIP breaks through state-of-the-arts GCL framework by designing a theoretically-guaranteed injective graph augmenter that can better preserve graph’s unique information and a multi-head encoder, which integrates both individual-specific and inter-graph proximity information.

We first review some background knowledge of GNN. Given a graph \(G=(\mathcal {V}, \mathcal {E})\) with raw node features \(X\in \mathcal {R}^{|\mathcal {V}|\times d_x}\), the feature updating process in GNN’s \(l\)th layer is as follows:where \(h_{v}^{(l)}\) is the hidden feature of node \(v\) in GNN’s \(l\)th layer and \(h_{v}^{(0)}\) is initialized as \(X_v\). \(\lbrace h_{u}^{(l-1)}: u \in \mathcal {N}(v)\rbrace\) is the multiset (a set allows possibly repeating elements) of the neighboring node features. \(\omega\) and \(\rho\) are the aggregation and updating functions, respectively. For example, in Graph Isomorphism Network (GIN) [Xu et al. 2018], the multi-layer perceptron (MLP) is used to fit the composition of aggregation and combination functions:where \(\epsilon\) is a learnable parameter or a fixed scalar. After \(L\) layers of iteration, the graph representation \(h_G\) is calculated asThe Readout function can be any permutation-invariant function such as summation or maximization.

We briefly introduce the WL graph isomorphism test [Weisfeiler and Leman 1968] to establish the groundwork for later theoretical research. Graph isomorphism problem aims at judging if two graphs have the same topology. However, no existing polynomial-time algorithm can solve this problem [Babai 2016]. The WL test is an effective algorithm to discern non-isomorphic graphs except for some corner examples [Cai et al. 1992]. Concretely, it comprises a two-step iterative process: for each node, (1) aggregate the labels from its neighborhood, and (2) use a hash function to map its label and the aggregated labels to a unique new label. The WL test decides two graphs as non-isomorphic once they have different label distributions in any iteration. It is noteworthy that this two-step process is strikingly similar to the aggregation and combination process in GNNs. Thus Xu et al. [2018] have investigated the link between GNNs and the WL test and proved that traditional GNNs are as most as powerful as the WL test, upon which we build our theoretical analysis later.

Recall that graph contrastive learning aims at preserving graph’s unique information by maximizing the mutual information between representations from different views. As a key component, a good graph augmenter should satisfy the following two properties: (1) adaptivity, i.e., learning informative augmented graphs according to the input graph distribution; (2) injectivity, i.e., for different input graphs, generating augmented graphs distinguishable by subsequent encoder and discriminator. We then provide our top-k graph augmenter, which satisfies these two properties.

Formally, assume that we are given a set of training graphs \(\lbrace G_n\rbrace _{n=1}^N\) in an input space \(\mathcal {G}\), with empirical probability distribution \(\mathcal {P}\). Let \(\Phi\) be a family of graph transformations (e.g., node dropping), \(\Psi\) be the parameter space and \(t_{\phi }^{\psi }:\mathcal {G}\rightarrow \mathcal {G}\) be a parametric function with transformation \(\phi \in \Phi\) and parameters \(\psi \in \Psi\) (e.g., a neural network). Then we define \(\mathcal {D}_{\phi ,\mathcal {P}}^{\psi }\) as the marginal distribution induced by pushing samples from \(\mathcal {P}\) through \(t_{\phi }^{\psi }\). In other words, \(\mathcal {D}_{\phi ,\mathcal {P}}^{\psi }\) is the distribution of augmented graphs \(t_{\phi }^{\psi }(G)\), where \(G\sim \mathcal {P}\). Then given two types of graph transformations \(\phi _i,\phi _j\in \Phi\), we aim at learning the parameters \(\psi _i\) and \(\psi _j\) to maximize the mutual information, i.e., \(I(\mathcal {D}_{\phi _i,\mathcal {P}}^{\psi _i}; \mathcal {D}_{\phi _j,\mathcal {P}}^{\psi _j})\). For simplicity, we signify \(\mathcal {D}_{\phi _i,\mathcal {P}}^{\psi _i}\) as \(v_i\) in the rest of article.

After determining the criteria of augmenter, we then provide an instantiation of obtaining \(t^{\psi _i}_{\phi _i}(G)\) and \(t^{\psi _j}_{\phi _j}(G)\) while leaving the optimization of \(I(v_i;v_j)\) to Section 4.2. Following [You et al. 2020], we consider four standard forms of graph transformations as \(\Phi\), including node dropping (ND), edge perturbation (EP), subgraph inducing (SI), and feature masking (FM). Specifically, the top-k augmenter consists of an augmentation encoder and four augmentation heads.

Augmentation encoder. For an input graph \(G=(\mathcal {V}, \mathcal {E})\) with node feature matrix \(X\in \mathcal {R}^{|\mathcal {V}|\times d_x}\), a GNN augmentation encoder \(g_\eta (\cdot): \mathcal {R}^{|\mathcal {V}| \times d_{x}} \times \mathcal {R}^{|\mathcal {V}|^2} \rightarrow \mathcal {R}^{|\mathcal {V}| \times d_{h}} \times \mathcal {R}^{d_{h}}\) shared by all the transformations learns node representations \(H_{v}\) and graph representation \(h_G\) to provide subsequent modules with expressive encodings. Specifically, it consists of a GNN producing node representations, a read-out function (summation) aggregating the representations into a graph representation, To encode graphs, we opt for expressive power and adopt Graph Isomorphism Network.

Top-k augmentation head. Given \(H_{v}\) and \(h_G\), we aim at learning the importance score of each node/edge and select the top-k ones that can preserve graph’s most unique information for each transformation. Specifically, we select the top-k important nodes which should be preserved/feature-preserved for ND/FM, the top-k important edges from all the node pairs for EP, and the top-one important node with its \(l\)-hop neighborhood as the subgraph for SI. Formally, for each \(\phi \in \Phi\), the propagation rule of the top-k augmentation head \(q_{\phi }(\cdot):\mathcal {G}\times \mathcal {R}^{|\mathcal {V}| \times d_{h}} \times \mathcal {R}^{d_{h}}\rightarrow \mathcal {G}\) is defined as follows:where \(\operatorname{C_n}\)/\(\operatorname{C_e}\) indicates the combination of node/edge and graph embeddings for node/edge selection and \(\mathbb {1}\) is the indicator function. For large graphs, \(C_e\) can be obtained from all the existing edges and randomly sampled non-existing edges. \(\operatorname{MLP}\) denotes the multi-layer perceptron. \(\mathbf {y_{n}^{\phi }} \in \mathcal {R}^{|\mathcal {V}|\times 1}\)/\(\mathbf {y_{e}^{\phi }}\in \mathcal {R}^{|\mathcal {V}|^2\times 1}\) denotes the node/edge scores and \(\operatorname{Rank}(\mathbf {y}, k)\) returns indices of the \(k\)-largest values in \(\mathbf {y}\). In practice, \(k_n\)/\(k_e\) is set as a ratio of node/edge numbers to fit different graph sizes. \(\mu _X^{\phi }\) and \(\mu _A^{\phi }\) are the transformation-specific functions for the augmented feature matrix \(X^{\phi }\) and adjacency matrix \(A^{\phi }\), respectively. For ND and SI, \(X^{ND}\)/\({X^{SI}}\) is the submatrix of \(X\) representing the features of top \(k^{ND}_n\) nodes or nodes in the \(l\)-hop subgraph centered by the top-one node. \(A^{ND}\)/\(A^{SI}\) contains the edges induced by preserved nodes with the sum of their corresponding node scores as edge weight. For EP, \(X^{EP}\) is identical to \(X\) while \(A^{EP}\) contains the selected \(k^{EP}_e\) edges weighted by edge scores. For FM, the features of the top \(k^{FM}_n\) nodes are preserved from \(X\) while others’ are masked with Gaussian noise. The edges in \(A^{FM}\) are identical to those in \(A\) while weighted in the same way as ND and SI. The detailed algorithms for the four augmentation heads can be referred to Appendix.

Crucially, by introducing edge weights to the augmented graphs, the top-k graph augmenter is not only trainable by back-propagation but also enjoys the injectivity. Note that according to Lemma 1, GNNs are never injective between the graph space and the representation space since GNN’s expressive power is limited by the WL test. Thus we slightly abuse the definition of “injectivity” and redefine it in the graph space.

Due to the limitation of GNN’s expressive power, we consider GNNs as powerful as the WL test, which satisfy the conditions in Lemma 2.

We define these GNNs as Injective GNN (I-GNN) and redefine the injectivity in the graph space.

Note that I-GNNs map graphs distinguishable by the WL test to different representations, while our top-k augmentation head can map the graph representations to different augmented graphs, bridging the gap from representation space to graph space. Specifically, with the I-GNN as the augmentation encoder, the top-k augmenter satisfies the injectivity.

The proof of Lemma 1, 2 can be referred to Xu et al. [2018] and that of Theorem 1 is provided in Appendix.

Given graph \(G\) and its \(M\) augmentations \(\lbrace G_{\phi _i}=t_{\phi _i}^{\psi _i}(G)\rbrace _{i=1}^{M}\) as input, the multi-head encoder aims at learning high-quality representations via MI maximization and inter-graph proximity preservation. To this end, we borrow ideas from multi-task learning whose architectures usually follow the same outline [Crawshaw 2020]: a shared feature extractor and an individual output branch for each task. Drawing on its essence, we employ a shared encoder with two projection heads supervised by the contrastive loss and proximity loss, respectively.

Shared encoder. We first pass \(\lbrace G_{\phi _i}\rbrace _{i=1}^{M}\) and \(G\) through a shared GNN encoder \(g_\theta (\cdot)\) to obtain their graph-level embeddings \(\lbrace h^{\prime }_{G_{\phi _i}}\!\rbrace _{i=1}^{M}\) and \(h^{\prime }_G\) as input of the projection heads. The architecture of shared encoder is the same with augmentation encoder.

Contrastive projection head. We use a non-linear transformation \(f_c(\cdot)\) to map the augmented graph embeddings \(\lbrace h^{\prime }_{G_{\phi _i}}\!\rbrace _{i=1}^{M}\) to a new latent space, i.e., \(z_i=f_c(h^{\prime }_{G_{\phi _i}}\!)\). Then for each pair of views \((i,j)\), we maximize the consistency between positive pairs \(z_i,z_j\) compared with negative pairs by optimizing the normalized temperature-scaled cross entropy loss (NT-Xent) [Oord et al. 2018] which is defined as follows:where \(N\) denotes the batch size, \(\operatorname{sim}(\cdot)\) denotes the cosine function and \(\tau\) is the temperature hyper-parameter. As proved in You et al. [2020], NT-Xent could fit the formulation of the InfoNCE loss [Oord et al. 2018]. Thus minimizing NT-Xent is equivalent to maximizing a lower bound of \(I(v_i;v_j)\). Supervised by NT-Xent, the top-k augmenter can learn informative views, enabling subsequent modules easier to optimize \(I(v_i;v_j)\). Thus the shared encoder can learn graph representations preserving the most graphs’ unique information.

Proximity projection head. Similar to the contrastive projection head, we apply another non-linear transformation \(f_p(\cdot)\) to map the original graph embedding \(h^{\prime }_G\) to another latent space, i.e., \(z=f_p(h^{\prime }_{G})\). Given the embeddings \(\lbrace z_n\rbrace _{n=1}^N\) of graph samples in a batch and a pre-defined proximity metric, we first use the metric to determine the proximity between all pairs of graphs in a batch, obtaining a proximity matrix \(S\). Then we force the similarity between any pair of graph embeddings \(z_n\) and \(z_{n^{\prime }}\) to be consistent with the values in \(S\) by optimizing the proximity loss:where \((n,n^{\prime })\) is sampled from a batch with equal probability. \(S\) can be derived from any graph kernel or domain knowledge while we find that the Weisfeiler-Lehman Subtree Kernel [Shervashidze et al. 2011] works well and make it a default choice of Ada-MIP.

Practically, two-layer perceptrons (MLP) are applied to model \(f_c\) and \(f_p\). Overall, the unsupervised loss iswhere \(\alpha \in [0, 1]\) is a hyper-parameter to control the contributions towards the overall objective. After training, we can simply maintain the shared encoder \(g_\theta\) for downstream tasks.

In this section, we analyze the complexity of Ada-MIP with GIN as the GNN encoder and the WL Subtree kernel as the preprocessing method. Suppose the number of nodes and edges in the input graph are \(N\) and \(M\) respectively. Let \(s\) denote the number of training epochs, \(B\) denote the size of each training batch, \(V\) denote the number of input graphs, \(d\) denote the embedding size, \(L\) denote the sum of GNN layers in augmentation and shared encoders.

Specifically, in the preprocessing phase, Ada-MIP adopts the WL Subtree kernel whose complexity is \(O(M)\) and pre-computes the proximity matrix of graphs in the same batch. Thus the complexity of preprocessing is \(O(\frac{V}{B}B^2M)=O(VBM)\). In the learning phase, Ada-MIP uses GIN as the graph encoders whose complexity is \(O(BLMd)\). As for contrastive learning, both the positive and negative samples are drawn from the augmented graphs from the same batch. Within a batch, the complexity of calculating Equation (5) is \(O(B^2d)\). As for proximity learning, the graph pairs are also sampled from the same batch and the complexity of calculating Equation (6) is also \(O(B^2d)\). Therefore, the time complexity of the whole training phase is \(O(s\frac{V}{B}(BLMd+B^2d))=O(sV(LMd+Bd))\) and the overall complexity of Ada-MIP is \(O(VBM+sV(LMd+Bd))\). It is notable that the time complexity of graph contrastive learning baselines (e.g., GraphCL [You et al. 2020], ADGCL [Yin et al. 2021]) in the experiments is also \(O(sV(LMd+Bd))\). Thus the time complexity of Ada-MIP is on par with the baselines. Also Notice that GVAE [Kipf and Welling 2016b], one of the unsupervised baselines, has \(O(sV(LMd+N^2d))\) time complexity due to the adjacency matrix reconstruction in the VAE framework, where \(N\) denotes the number of nodes in the graphs. Since \(M\ll N^2\) for sparse graphs, our proposed method is much more scalable than GVAE.

For the unsupervised learning scenario, we evaluate Ada-MIP for graph classification on five biochemical datasets and four social network datasets from the standard TU Benchmark [Morris et al. 2020]. Table 1 shows their statistics and properties. For the semi-supervised learning scenario, we evaluate Ada-MIP for molecular property prediction on the benchmark QM9 dataset [Ramakrishnan et al. 2014]. QM9 dataset consists of about 134,000 drug-like organic molecules with a wide range of chemical compositions and characteristics. All of the molecules in the dataset are made up of Hydrogen (H), Carbon (C), Oxygen (O), Nitrogen (N), and Flourine (F) atoms. For each molecule, a total of 12 fundamental chemical characteristics are pre-computed. A more detailed description of the QM9 dataset can be referred to Gilmer et al. [2017]. Following InfoGraph* [Sun et al. 2019], we randomly select 5,000 samples as labeled training data, another 10,000 for validation, 10,000 for testing, and the rest as unlabeled training data. We use the same data split for all the methods. All the targets are normalized to have mean 0 and variance 1.

In the unsupervised experiments, we use the Graph Isomorphism Network (GIN) [Xu et al. 2018] as the encoder. We follow InfoGraph [Sun et al. 2019] and MVGRL [Hassani and Khasahmadi 2020] for graph classification and choose the number of GNN layers, number of epochs, and learning rate from \(\lbrace 3,5,7\rbrace\), \(\lbrace 10,20,50,100,300\rbrace\) and \(\lbrace 1e-3,5e-4,1e-4\rbrace\), respectively. The hidden dimension, batch size, and the C parameter of SVM are fixed as \(64, 128\) and 10. Both the projection heads are parameterized by 2-layered feed-forward neural networks. Following each linear layer is a ReLU activation function.

In the semi-supervised experiments, we follow InfoGraph* [Sun et al. 2019] for molecular property prediction and use enn-s2s [Gilmer et al. 2017] with the number of set2set computations as 3. All the involved models are trained with an initial learning rate 0.001 for 500 epochs with a batch size 20 and \(\lambda =10^{-3}\).

In all the experiments, we set the hyper-parameters involved by Ada-MIP as a fixed value. We set the sampling ratio \(k\) of nodes/edges in the ND, EP, and FM augmentation heads as 0.9 and the hop number \(l\) in SI head as 2. We fix \(\tau\) in NT-Xent as 0.2, \(\alpha\) in Equation (7) as 0.005 and \(\lambda\) in Equation (10) as 0.001.

For unsupervised learning, we compare Ada-MIP with four graph kernel baselines including Shortest Path Kernel (SP) [Borgwardt and Kriegel 2005], Weisfeiler-Lehman Sub-tree Kernel (WL) [Shervashidze et al. 2011], Pyramid Match Kernel (PM) [Nikolentzos et al. 2017], Multi-scale Laplacian kernel (MLG) [Kondor and Pan 2016], three unsupervised graph-level representation learning baselines including Node2vec [Grover and Leskovec 2016], Sub2vec [Adhikari et al. 2018], Graph2vec [Narayanan et al. 2017], and nine self-supervised learning baselines including GVAE [Kipf and Welling 2016b], InfoGraph [Sun et al. 2019], GraphCL [You et al. 2020], JOAO [You et al. 2021], MVGRL [Hassani and Khasahmadi 2020], AD-GCL [Suresh et al. 2021], GASSL [Yang et al. 2021], AutoGCL [Yin et al. 2021], SimGRACE [Xia et al. 2022]. In order to make fair comparisons with these baseline methods, we directly quote the results from the previous literature or their original articles if available. If results are not previously reported, we implement them based on the public source codes and conduct a hyperparameter search according to the original article.

For semi-supervised learning, We consider the three proposed models mentioned in Section 5 and compare them with several baselines: (1) the supervised GNN (Sup-GNN) providing an anchor of the performance. (2) InfoGraph*, (3) GraphCL, (4) MVGRL, and (5) AD-GCL. For a fair comparison, we embed all the baselines into InfoGraph* using the same hyper-parameters and implement \(\ell _{m}\) in Equation (8) as the JS estimator. For GraphCL, we choose ND and FM as the two graph transformations, which have been empirically proved to perform the best [Zhu et al. 2021a].

In this part, we investigate the effectiveness of the proposed Ada-MIP in unsupervised learning scenario, which focuses on the downstream graph classification task. Following previous works, we compute the accuracy using LIBSVM [Chang and Lin 2011] and perform 10-fold cross-validations. All the experiments are repeated 5 times. We report the average accuracy and standard deviation for each dataset in Table 2, where we see that the proposed method achieves better or comparable results than the baseline methods. In particular, Ada-MIP outperforms the SOTA methods by a maximum of 3.1% and an average of 1.5% on 7 of the 9 benchmark datasets. This indicates the high quality of graph representations learned by Ada-MIP in the unsupervised scenario.

In this part, we investigate the effectiveness of the proposed Ada-MIP in a semi-supervised learning scenario, which focuses on the molecular property prediction task. Following InfoGraph*, we optimize the mean square error (MSE) loss while evaluating the mean absolute error (MAE). We report the MAE for each task in Table 3, where we see that simply using Ada-MIP yields the best performance on 10 out of 12 tasks compared to all the baselines, which again validates the superiority of Ada-MIP. Furthermore, by applying adversarial learning on the augmenter, the performance on 11 out of 12 tasks is further boosted by Ada-MIP-AD and Ada-MIP-SAD, which demonstrates that filtering out the task-irrelevant information between views is able to fully leverage the valuable labels. Besides, the superior performance of Ada-MIP-SAD also indicates its effectiveness with less cost than Ada-MIP-AD. In practice, Ada-MIP-SAD is a good tradeoff between efficiency and effectiveness.

Besides, to validate the convergence of Ada-MIP-AD, we draw the training curves for all the loss items in Equation (10) on the QM9 dataset. The results in Figure 4 show that the training process is stable and all the loss items converge after 200 epochs.

Effect of Components in Ada-MIP. We first investigate the contributions of each component in Ada-MIP by removing the contrastive head, the proximity head, and the top-k graph augmenter, respectively. Specifically, Ada-MIP w/o CH denotes the model that only optimizes the proximity loss. Ada-MIP w/o PH denotes the model that optimizes the contrastive loss with the top-k augmenter. Ada-MIP w/o TGA denotes the model that simultaneously optimizes the above two losses while replacing the top-k augmenter with a stochastic augmentation strategy as the same as GraphCL. The results are shown at the top of Table 4.

It is observed that simply optimizing the proximity loss can boost the performance of the WL Subtree kernel. This is because the graph encoder maps the inter-graph information into low-dimensional embeddings, leading to better generalization performance on downstream tasks. Besides, the consistent superior performance of Ada-MIP w/o PH over Ada-MIP w/o CH implies that learning graphs’ unique features benefits downstream tasks more compared to learning common features. Moreover, Although the optimization object of contrastive loss and proximity loss is quite different, they are complementary and combining them can further boost the model performance. Overall, Ada-MIP consistently has a significant improvement over its three incomplete versions, indicating that all the three components are essential in Ada-MIP.

Effect of Graph Kernel Methods. It might be argued that the performance improvement by Ada-MIP mainly depends on the choice of graph kernel methods. Thus in this part, we investigate the effect of Ada-MIP with three other graph kernels SP, PM, and MLG. The results shown in the middle of Table 4 suggest that Ada-MIP can also achieve performance gain with graph kernels other than WL. And the consistent best performance of Ada-MIP with WL also suggests that WL is a sweet default choice for Ada-MIP.

Effect of View Numbers. To investigate the relationship between view numbers and the quality of learned representations in Ada-MIP, we evaluate all the pairs and triplets of augmentation combinations on five datasets and report the average and best results in Table 4. Overall, we observe that the average accuracy of Ada-MIP increases as the number of views grows on all datasets. Even considering all the combinations of views, Ada-MIP with full views still performs the best on 3 out of 5 datasets. From another perspective, Ada-MIP with two views is still competitive to the baselines, implying a good tradeoff between effectiveness and efficiency.

We first investigate Ada-MIP’s sensitivity to \(\alpha\) in Equation (7). Different \(\alpha\) controls the relative learning pace of the two objectives. We tune \(\alpha\) from \(\lbrace 0.001,0.005,0.01,0.05\rbrace\) and report the results on the top of Table 5. We find that Ada-MIP is robust to different \(\alpha\) within a reasonable range.

We then investigate the hyper-parameter in each augmentation head of the graph augmenter. While experimenting on one head, we drop out all the other augmentation heads and the proximity projection head as a vanilla version of Ada-MIP. We contrast the augmented graphs with original graphs and tune the ratio of node/edge selection \(k\) from \(\lbrace 0.95, 0.9, 0.85, 0.8\rbrace\) and the hops of the induced sub-graph \(l\) from \(\lbrace 1,2,3\rbrace\). Table 5 shows that the vanilla Ada-MIP also consistently outperforms GraphCL and AutoGCL on all the datasets, which validates the effectiveness of our top-k augmenter. Besides, we also observe that our augmenter is robust to the slight tuning of the hyper-parameters \(k\) and \(l\).

To validate our theoretical analysis of the top-k augmenter’s injectivity, we draw the four contrastive loss curves of Ada-MIP and GraphCL for different augmentations on the PROTEINS dataset. We argue that if an augmenter maps more non-isomorphic graphs to augmented graphs distinguishable by subsequent encoder and discriminator, it can better help to optimize the contrastive loss. To ensure a fair comparison, we apply the vanilla Auot-MIP mentioned in Section 6.7 and the same hyper-parameter settings for Ada-MIP and GraphCL. Figure 5 shows that the vanilla Ada-MIP can consistently optimize the lower bound of mutual information better than GraphCL. This result consolidates that the top-k augmenter with each augmentation head can learn more informative views than those generated by the fixed augmentation strategy in GraphCL.

We study the efficiency of the proposed method by taking two datasets, i.e., RDT-B and DD as examples. This experiment is run on a server with NVIDIA GeForce RTX 1080 Ti (11 GB). We set the same hyper-parameters and run 300 epochs for all the test methods. The results measured in wall-clock time in seconds are presented in Table 6, where we compare the proposed Ada-MIP with GraphCL and GVAE. Particularly, we report the results w.r.t. the total running time of all the methods and the mean training time per epoch, including forward pass, objective loss calculation, and backward pass. GraphCL needs the least training time as it uses random augmentations and simply optimizes the contrastive loss. GVAE costs the most time since it has to reconstruct the adjacency matrix of each graph. Ada-MIP ranks second and achieves slightly inferior to GraphCL as it requires precomputing the proximity matrix, learning the augmented views, and optimizing the proximity loss. However, it is observed that Ada-MIP only spends less than 2% additional training time on preprocessing. And the training efficiency performance of Ada-MIP is quite close to the results of GraphCL. Considering the prediction accuracy on downstream tasks, our proposed method consumes reasonable training time and achieves superior results.

To better interpret the learned augmentations by the top-k augmenter, we randomly select three graphs in the MUTAG dataset and visualize their augmentations in Figure 6. The model is trained for 100 epochs and we set \(k=0.9\) for ND, ED, and FM and \(l=2\) for SI. From the results, we have several observations. First, the top-k augmenter tends to preserve the connectivity of augmented graphs for ND and the feature of special atoms like oxygen and nitrogen for FM. Second, the center nodes have higher importance scores in the augmented graphs of SI, indicating that the augmenter tends to choose the subgraphs of larger size and preserve as much information of the original graph. Third, for all the transformations, the top-k augmenter can identify and preserve some key chemical groups such as nitro and hydroxide radical, which might be important to the mutagenic property of chemicals.