Contrastive Multi-View Representation Learning on Graphs

Introduction

Graph neural networks (GNN) (Li et al., 2015; Gilmer et al., 2017; Kipf & Welling, 2017; Veličković et al., 2018; Xu et al., 2019b) reconcile the expressive power of graphs in modeling interactions with unparalleled capacity of deep models in learning representations. They process variable-size permutation-invariant graphs and learn low-dimensional representations through an iterative process of transferring, transforming, and aggregating the representations from topological neighbors. Each iteration expands the receptive field by one-hop and after $k$ iterations the nodes within $k$-hops influence one another (Khasahmadi et al., 2020). GNNs are applied to data with arbitrary topology such as point clouds (Hassani & Haley, 2019), meshes (Wang et al., 2018), robot designs (Wang et al., 2019), physical processes (Sanchez-Gonzalez et al., 2018), social networks (Kipf & Welling, 2017), molecules (Duvenaud et al., 2015), and knowledge graphs (Vivona & Hassani, 2019). For an overview see (Zhang et al., 2020; Wu et al., 2020).

GNNs mostly require task-dependent labels to learn rich representations. Nevertheless, annotating graphs is challenging compared to more common modalities such as video, image, text, and audio. This is partly because graphs are usually used to represent concepts in specialized domains, e.g., biology. Also, labeling graphs procedurally using domain knowledge is costly (Sun et al., 2020). To address this, unsupervised approaches such as reconstruction based methods (Kipf & Welling, 2016) and contrastive methods (Li et al., 2019) are coupled with GNNs to allow them learn representations without relying on supervisory data. The learned representations are then transferred to a priori unknown down-stream tasks. Recent works on contrastive learning by maximizing mutual information (MI) between node and graph representations have achieved state-of-the-art results on both node classification (Veličković et al., 2019) and graph classification (Sun et al., 2020) tasks. Nonetheless, these methods require specialized encoders to learn graph or node level representations.

Recent advances in multi-view visual representation learning (Tian et al., 2019; Bachman et al., 2019; Chen et al., 2020), in which composition of data augmentations is used to generate multiple views of a same image for contrastive learning, has achieved state-of-the-art results on image classification benchmarks surpassing supervised baselines. However, it is not clear how to apply these techniques to data represented as graphs. To address this, we introduce a self-supervised approach to train graph encoders by maximizing MI between representations encoded from different structural views of graphs. We show that our approach outperforms previous self-supervised models with significant margin on both node and graph classification tasks without requiring specialized architectures. We also show that when compared to supervised baselines, it performs on par with or better than strong baselines on some benchmarks.

To further improve contrastive representation learning on node and graph classification tasks, we systematically study the major components of our framework and surprisingly show that unlike visual contrastive learning: (1) increasing the number of views, i.e., augmentations, to more than two views does not improve the performance and the best performance is achieved by contrasting encodings from first-order neighbors and a general graph diffusion, (2) contrasting node and graph encodings across views achieves better results on both tasks compared to contrasting graph-graph or multi-scale encodings, (3) a simple graph readout layer achieves better performance on both tasks compared to hierarchical graph pooling methods such as differentiable pooling (DiffPool) (Ying et al., 2018), and (4) applying regularization (except early-stopping) or normalization layers has a negative effect on the performance.

Using these findings, we achieve new state-of-the-art in self-supervised learning on 8 out of 8 node and graph classification benchmarks under the linear evaluation protocol. For example, on Cora node classification benchmark, our approach achieves 86.8% accuracy, which is a 5.5% relative improvement over previous state-of-the-art (Veličković et al., 2019), and on Reddit-Binary graph classification benchmark, it achieves 84.5% accuracy, i.e., a 2.4% relative improvement over previous state-of-the-art (Sun et al., 2020). When compared to supervised baselines, our approach performs on par with or better than strong supervised baselines, e.g., graph isomorphism network (GIN) (Xu et al., 2019b) and graph attention network (GAT) (Veličković et al., 2018), on 4 out of 8 benchmarks. As an instance, on Cora (node) and IMDB-Binary (graph) classification benchmarks, we observe 4.5% and 5.3% relative improvements over GAT, respectively.

Related Work

Random walks (Perozzi et al., 2014; Tang et al., 2015; Grover & Leskovec, 2016; Hamilton et al., 2017) flatten graphs into sequences by taking random walks across nodes and use language models to learn node representations. They are shown to over-emphasize proximity information at the expense of structural information (Veličković et al., 2019; Ribeiro et al., 2017). Also, they are limited to transductive settings and cannot use node features (You et al., 2019). Graph kernels (Borgwardt & Kriegel, 2005; Shervashidze et al., 2009, 2011; Yanardag & Vishwana, 2015; Kondor & Pan, 2016; Kriege et al., 2016) decompose graphs into sub-structures and use kernel functions to measure graph similarity between them. Nevertheless, they require non-trivial task of devising similarity measures between substructures. Graph autoencoders (GAE) (Kipf & Welling, 2016; Garcia Duran & Niepert, 2017; Wang et al., 2017; Pan et al., 2018; Park et al., 2019) train encoders that impose the topological closeness of nodes in the graph structure on the latent space by predicting the first-order neighbors. GAEs over-emphasize proximity information (Veličković et al., 2019) and suffer from unstructured predictions (Tian et al., 2019). Contrastive methods (Li et al., 2019; Veličković et al., 2019; Sun et al., 2020) measure the loss in latent space by contrasting samples from a distribution that contains dependencies of interest and the distribution that does not. These methods are the current state-of-the-art in unsupervised node and graph classification tasks. Deep graph Infomax (DGI) (Veličković et al., 2019) extends deep InfoMax (Hjelm et al., 2019) to graphs and achieves state-of-the-art results in node classification benchmarks by learning node representations through contrasting node and graph encodings. InfoGraph (Sun et al., 2020), on the other hand, extends deep InfoMax to learn graph-level representations and outperforms previous models on unsupervised graph classification tasks. Although these two methods use the same contrastive learning approach, they utilize specialized encoders.

2 Graph Diffusion Networks

Graph diffusion networks (GDN) reconcile spatial message passing and generalized graph diffusion (Klicpera et al., 2019b) where diffusion as a denoising filter allows messages to pass through higher-order neighborhoods. GDNs can be categorized to early- and late- fusion models based on the stage the diffusion is used. Early-fusion models (Xu et al., 2019a; Jiang et al., 2019) use graph diffusion to decide the neighbors, e.g., graph diffusion convolution (GDC) replaces adjacency matrix in graph convolution with a sparsified diffusion matrix (Klicpera et al., 2019b), whereas, late-fusion models (Tsitsulin et al., 2018; Klicpera et al., 2019a) project the node features into a latent space and then propagate the learned representation based on a diffusion.

3 Learning by Mutual Information Maximization

InfoMax principle (Linsker, 1988) encourages an encoder to learn representations that maximizes the MI between the input and the learned representation. Recently, a few self-supervised models inspired by this principle are proposed which estimate the lower bound of the InfoMax objective, e.g., using noise contrastive estimation (Gutmann & Hyvärinen, 2010), across representations. Contrastive predictive coding (CPC) (Oord et al., 2018) contrasts a summary of ordered local features to predict a local feature in the future whereas deep InfoMax (DIM) (Hjelm et al., 2019) simultaneously contrasts a single summary feature, i.e., global feature, with all local features. Contrastive multiview coding (CMC) (Tian et al., 2019), augmented multi-scale DIM (AMDIM) (Bachman et al., 2019), and SimCLR (Chen et al., 2020) extend the InfoMax principle to multiple views and maximize the MI across views generated by composition of data augmentations. Nevertheless, it is shown that success of these models cannot only be attributed to the properties of MI alone, and the choice of encoder and MI estimators have a significant impact on the performance (Tschannen et al., 2020).

Method

Inspired by recent advances in multi-view contrastive learning for visual representation learning, our approach learns node and graph representations by maximizing MI between node representations of one view and graph representation of another view and vice versa which achieves better results compared to contrasting global or multi-scale encodings on both node and graph classification tasks (see section 4.4). As shown in Figure 1, our method consists of the following components:

An augmentation mechanism that transforms a sample graph into a correlated view of the same graph. We only apply the augmentation to the structure of the graphs and not the initial node features. This is followed by a sampler that sub-samples identical nodes from both views, i.e., similar to cropping in visual domain.

Two dedicated GNNs, i.e., graph encoders, one for each view, followed by a shared MLP, i.e., projection head, to learn node representations for both views.

A graph pooling layer, i.e., readout function, followed by a shared MLP, i.e., projection head, to learn graph representations for both views.

A discriminator that contrasts node representations from one view with graph representation from another view and vice versa, and scores the agreement between them.

Recent works in self-supervised visual representation learning suggest that contrasting congruent and incongruent views of images allows encoders to learn rich representations (Tian et al., 2019; Bachman et al., 2019). Unlike images in which views are generated by standard augmentations, e.g., cropping, rotating, distorting colors, etc., defining views on graphs is not a trivial task. We can consider two types of augmentations on graphs: (1) feature-space augmentations operating on initial node features, e.g., masking or adding Gaussian noise, and (2) structure-space augmentations and corruptions operating on graph structure by adding or removing connectivities, sub-sampling, or generating global views using shortest distances or diffusion matrices. The former augmentation can be problematic as many benchmarks do not carry initial node features. Moreover, we observed that masking or adding noise on either spaces degrades the performance. Hence, we opted for generating a global view followed by sub-sampling.

We empirically show that in most cases the best results are achieved by transforming an adjacency matrix to a diffusion matrix and treating the two matrices as two congruent views of the same graph’s structure (see section 4.4). We speculate that because adjacency and diffusion matrices provide local and global views of a graph structure, respectively, maximizing agreement between representation learned from these two views allows the model to simultaneously encode rich local and global information.

For sub-sampling, we randomly sample nodes and their edges from one view and select the exact nodes and edges from the other view. This procedure allows our approach to be applied to inductive tasks with graphs that do not fit into the GPU memory and also to transductive tasks by considering sub-samples as independent graphs.

2 Encoders

3 Training

In order to train the encoders end-to-end and learn rich node and graph level representations that are agnostic to down-stream tasks, we utilize the deep InfoMax (Hjelm et al., 2019) approach and maximize the MI between two views by contrasting node representations of one view with graph representation of the other view and vice versa. We empirically show that this approach consistently outperforms contrasting graph-graph or multi-scale encodings on both node and graph classifications benchmarks (see section 4.4). We define the objective as follows:

where ${\theta,\omega,\phi,\psi}$ are graph encoder and projection head parameters, ${|\mathcal{G}|}$ is the number of graphs in train set or number of sub-sampled graphs in transductive setting, ${|g|}$ is the number of nodes in graph $g$, and $\vec{h}_{i}^{\alpha},\vec{h}_{g}^{\beta}$ are representations of node $i$ and graph $g$ encoded from views $\alpha,\beta$, respectively.

Experimental Results

We use three node classification and five graph classification benchmarks widely used in the literature (Kipf & Welling, 2017; Veličković et al., 2018, 2019; Sun et al., 2020). For node classification, we use Citeseer, Cora, and Pubmed citation networks (Sen et al., 2008) where documents (nodes) are connected through citations (edges). For graph classification, we use the following: MUTAG (Kriege & Mutzel, 2012) containing mutagenic compounds, PTC (Kriege & Mutzel, 2012) containing compounds tested for carcinogenicity, Reddit-Binary (Yanardag & Vishwana, 2015) connecting users (nodes) through responses (edges) in Reddit online discussions, and IMDB-Binary and IMDB-Multi (Yanardag & Vishwana, 2015) connecting actors/actresses (nodes) based on movie appearances (edges). The statistics are summarized in Table 1.

2 Evaluation Protocol

For both node and graph classification benchmarks, we evaluate the proposed approach under the linear evaluation protocol and for each task, we closely follow the experimental protocol of the previous state-of-the-art approaches. For node classification, we follow DGI and report the mean classification accuracy with standard deviation on the test nodes after 50 runs of training followed by a linear model. For graph classification, we follow InfoGraph and report the mean 10-fold cross validation accuracy with standard deviation after 5 runs followed by a linear SVM. The linear classifier is trained using cross validation on training folds of data and the best mean classification accuracy is reported. Moreover, for node classification benchmarks, we evaluate the proposed method under clustering evaluation protocol and cluster the learned representations using K-Means algorithm. Similar to (Park et al., 2019), we set the number of clusters to the number of ground-truth classes and report the average normalized MI (NMI) and adjusted rand index (ARI) for 50 runs.

We initialize the parameters using Xavier initialization (Glorot & Bengio, 2010) and train the model using Adam optimizer (Kingma & Ba, 2014) with an initial learning rate of 0.001. To have fair comparisons, we follow InfoGraph for graph classification and choose the number of GCN layers, number of epochs, batch size, and the C parameter of the SVM from , , , and $[10^{-3}$, $10^{-2}$, …, $10^{2}$, $10^{3}$], respectively. For node classification, we follow DGI and set the number of GCN layers and the number of epochs and to 1 and 2,000, respectively, and choose the batch size from . We also use early stopping with a patience of 20. Finally, we set the size of hidden dimension of both node and graph representations to 512. For chosen hyper-parameters see Appendix.

3 Comparison with State-of-the-Art

To evaluate node classification under the linear evaluation protocol, we compare our results with unsupervised models including DeepWalk (Perozzi et al., 2014) and DGI. We also train a GAE (Kipf & Welling, 2016), a variant of DGI with a GDC encoder, and a variant of VERSE (Tsitsulin et al., 2018) by minimizing KL-divergence between node representations and diffusion matrix. Furthermore, we compare our results with supervised models including an MLP, iterative classification algorithm (ICA) (Lu & Getoor, 2003), label propagation (LP) (Zhu et al., 2003), manifold regularization (ManiReg) (Belkin et al., 2006), semi-supervised embedding (SemiEmb) (Weston et al., 2012), Planetoid (Yang et al., 2016), Chebyshev (Defferrard et al., 2016), mixture model networks (MoNet) (Monti et al., 2017), JK-Net, GCN, and GAT. The results reported in Table 2 show that we achieve state-of-the-art results with respect to previous unsupervised models. For example, on Cora, we achieve 86.8% accuracy, which is a 5.5% relative improvement over previous state-of-the-art. When compared to supervised baselines, we outperform strong supervised baselines: on Cora and PubMed benchmarks we observe 4.5% and 1.4% relative improvement over GAT, respectively.

To evaluate node classification under the clustering protocol, we compare our model with models reported in (Park et al., 2019) including: variational GAE (VGAE) (Kipf & Welling, 2016), marginalized GAE (MGAE) (Wang et al., 2017), adversarially regularized GAE (ARGA) and VGAE (ARVGA) (Pan et al., 2018), and GALA (Park et al., 2019). The results shown in Table 3 suggest that our model achieves state-of-the-art NMI and ARI scores across all benchmarks.

To evaluate graph classification under the linear evaluation protocol, we compare our results with five graph kernel methods including shortest path kernel (SP) (Borgwardt & Kriegel, 2005), Graphlet kernel (GK) (Shervashidze et al., 2009), Weisfeiler-Lehman sub-tree kernel (WL) (Shervashidze et al., 2011), deep graph kernels (DGK) (Yanardag & Vishwana, 2015), and multi-scale Laplacian kernel (MLG) (Kondor & Pan, 2016) reported in (Sun et al., 2020). We also compare with five supervised GNNs reported in (Xu et al., 2019b) including GraphSAGE (Hamilton et al., 2017), GCN, GAT, and two variants of GIN: GIN-0 and GIN-$\epsilon$. Finally, We compare the results with five unsupervised methods including random walk (Gärtner et al., 2003), node2vec (Grover & Leskovec, 2016), sub2vec (Adhikari et al., 2018), graph2vec (Narayanan et al., 2017), and InfoGraph. The results shown in Table 4 suggest that our approach achieves state-of-the-art results with respect to unsupervised models. For example, on Reddit-Binary (Yanardag & Vishwana, 2015), it achieves 84.5% accuracy, i.e., a 2.4% relative improvement over previous state-of-the-art. Our model also outperforms kernel methods in 4 out of 5 datasets and also outperforms best supervised model in one of the datasets. When compared to supervised baselines individually, our model outperforms GCN and GAT models in 3 out of 5 datasets, e.g., a 5.3% relative improvement over GAT on IMDB-Binary dataset.

It is noteworthy that we achieve the state-of-the-art results on both node and graph classification benchmarks using a unified approach and unlike previous unsupervised models (Veličković et al., 2019; Sun et al., 2020), we do not devise a specialized encoder for each task.

4 Ablation Study

We investigated four MI estimators including: noise-contrastive estimation (NCE) (Gutmann & Hyvärinen, 2010; Oord et al., 2018), Jensen-Shannon (JSD) estimator following formulation in (Nowozin et al., 2016), normalized temperature-scaled cross-entropy (NT-Xent) (Chen et al., 2020), and Donsker-Varadhan (DV) representation of the KL-divergence (Donsker & Varadhan, 1975). The results shown in Table 5 suggests that Jensen-Shannon estimator achieves better results across all graph classification benchmarks, whereas in node classification benchmarks, NCE achieves better results in 2 out of 3 datasets.

4.2 Effect of Contrastive Mode

We considered five contrastive modes including: local-global, global-global, multi-scale, hybrid, and ensemble modes. In local-global mode we extend deep InfoMax (Hjelm et al., 2019) and contrast node encodings from one view with graph encodings from another view and vice versa. Global-global mode is similar to (Li et al., 2019; Tian et al., 2019; Chen et al., 2020) where we contrast graph encodings from different views. In multi-scale mode, we contrast graph encodings from one view with intermediate encodings from another view and vice versa, and we also contrast intermediate encodings from one view with node encodings from another view and vice versa. We use two DiffPool layers to compute the intermediate encodings. The first layer projects nodes into a set of clusters where the number of clusters, i.e., motifs, is set as 25% of the number of nodes before applying DiffPool, whereas the second layer projects the learned cluster encodings into a graph encoding. In hybrid mode, we use both local-global and global-global modes. Finally, in ensemble mode, we contrast nodes and graph encodings from a same view for all views.

Results reported in Table 5 suggest that contrasting node and graph encodings consistently perform better across benchmarks. The results also reveal important differences between graph and visual representation learning: (1) in visual representation learning, contrasting global views achieves best results (Tian et al., 2019; Chen et al., 2020), whereas for graphs, contrasting node and graph encodings achieves better performance for both node and graph classification tasks, and (2) contrasting multi-scale encodings helps visual representation learning (Bachman et al., 2019) but has a negative effect on graph representation learning.

4.3 Effect of Views

We investigated four structural views including adjacency matrix, PPR and heat diffusion matrices, and pair-wise distance matrix where adjacency conveys local information and the latter three capture global information. Adjacency matrix is processed into a symmetrically normalized adjacency matrix (see section 3.2), and PPR and heat diffusion matrices are computed using Eq. (3) and (2), respectively. The shortest pair-wise distance matrix is computed by Floyd-Warshall algorithm, inversed in an element-wise fashion, and row-normalized using softmax. All views are computed once in preprocessing. The results shown in Table 5 suggest that contrasting encodings from adjacency and PPR views performs better across the benchmarks.

Furthermore, we investigated whether increasing the number of views increases the performance on down-stream tasks, monotonically. Following (Tian et al., 2019), we extended number of views to three by anchoring the main view on adjacency matrix and considering two diffusion matrices as other views. The results (see Appendix) suggest that unlike visual representation learning, extending the views does not help. We speculate this is because different diffusion matrices carry similar information about the graph structure. We also followed (Chen et al., 2020) and randomly sampled 2 out of 4 views for each training sample in each mini-batch and contrasted the representation. We observed that unlike visual domain, it degraded the performance.

4.4 Negative Sampling & Regularization

We investigated the performance with respect to batch size where a batch of size $N$ consists of $N-1$ negative and 1 positive examples. We observed that in graph classification, increasing the batch size slightly improves the performance, whereas, in node classification, it does not have a significant effect. Thus we opted for efficient smaller batch sizes. To generate negative samples in node classification, we considered two corruption functions: (1) random feature permutation, and (2) adjacency matrix corruption. We observed that applying the former achieves significantly better results compared to the latter or a combination of both.

Furthermore, we observed that applying normalization layers such as BatchNorm (Ioffe & Szegedy, 2015) or LayerNorm (Ba et al., 2016), or regularization methods such as adding Gaussian noise, L2 regularization, or dropout (Srivastava et al., 2014) during the pre-training degrades the performance on down-stream tasks (except early stopping).

Conclusion

We introduced a self-supervised approach for learning node and graph level representations by contrasting encodings from two structural views of graphs including first-order neighbors and a graph diffusion. We showed that unlike visual representation learning, increasing the number of views or contrasting multi-scale encodings do not improve the performance. Using these findings, we achieved new state-of-the-art in self-supervised learning on 8 out of 8 node and graph classification benchmarks under the linear evaluation protocol and outperformed strong supervised baselines in 4 out of 8 benchmarks. In future work, we are planning to investigate large pre-training and transfer learning capabilities of the proposed method.

References

Appendix

The model is implemented with PyTorch and each benchmark is run on a single GPU. For a given dataset, the node features are processed as follows. If the dataset contains initial node features, they are normalize using the standard score. If the dataset does not contains initial node features, but carries node labels, they are used as the initial node features (only in graph classification benchmarks). Otherwise, if the dataset has neither, the node features are initialized with node degrees. Diffusion and pair-wise distance matrices are computed once in preprocessing step using NetworkX and Numpy packages. The shortest pair-wise distance matrix is computed by Floyd-Warshall algorithm, inversed in an element-wise fashion, and row-normalized using softmax.

2 Hyper-Parameters

In out experiments, we fixed $\alpha$=0.2 and $t$=5 for PPR and heat diffusion, respectively. We used grid search to choose the hyper-parameters from the following ranges. For graph classification, we chose the number of GCN layers, number of epochs, batch size, and the C parameter of the SVM from , , , and $[10^{-3}$, $10^{-2}$, …, $10^{2}$, $10^{3}$], respectively. For node classification, we set the number of GCN layers and the number of epochs and to 1 and 2,000, respectively, and choose the batch size from . We also use early stopping with a patience of 20. Finally, we set the size of hidden dimension of both node and graph representations to 512. The selected parameters are reported in Table 6.

3 Effect of Number of Views

Furthermore, we investigated whether increasing the number of views increases the performance on down-stream tasks, monotonically. We extended number of views to three by anchoring the main view on adjacency matrix and considering two diffusion matrices, i.e, PPR and heat, as other views. The results shown in Table 7 suggest that unlike visual representation learning, extending the views does not improve the performance on the down-stream tasks. We speculate this is because different diffusion matrices carry similar information about the graph structure and hence using more of them does not introduce useful signals.

4 Effect of Pooling

In addition to mentioned sum pooling, we tried mean pooling and two variants of DiffPool: (1) DiffPool-1 where we use a single layer of DiffPool to aggregate all node representations into a single graph representation, and (2) DiffPool-2 where we use two DiffPool layers to compute the intermediate representations. The first layer projects nodes into a set of clusters, i.e., motifs, where the number of clusters is set as 25% of the number of nodes before applying DiffPool, whereas the second layer projects the learned cluster representations into a single graph representations. It is noteworthy that to train the model with Diffpool layers, we jointly optimize the contrastive loss with an auxiliary link prediction loss and an entropy regularization. The results shown in Table 6 suggest that sum pooling outperforms other pooling layers in 6 out of 8 benchmarks ,i.e., 5 out of 5 graph classification and 1 out if 3 node classification benchmarks. Also, results suggest that mean pooling achieves better results in 2 out of 3 node classification benchmarks.

5 Effect of Encoder

We also investigated the effect of assigning a dedicated encoder for each view or sharing an encoder across views. The results in Table 6 show that using a dedicated encoder for each view consistently achieves better results across all benchmarks. When using shared encoder, we also randomly sampled 2 out 4 views for each training sample in each mini-batch and contrasted the representation. We observed that unlike visual domain, it degraded the performance.

6 Effect of Negative Samples

Considering the importance of the number of negative samples in contrastive learning, we investigated the effect of batch size on the mode performance. For graph classification benchmarks, we used batch sizes of and for classification benchmarks we evaluated batch sizes of . As shown in Figure 2, we observe that increasing the batch size slightly increases the performance on graph classification task but has an negligible effect on the node classification.