  Graph contrastive learning attracts/disperses node representations for
similar/dissimilar node pairs under some notion of similarity. It may be
combined with a low-dimensional embedding of nodes to preserve intrinsic and
structural properties of a graph. In this paper, we extend the celebrated
Laplacian Eigenmaps with contrastive learning, and call them COntrastive
Laplacian EigenmapS (COLES). Starting from a GAN-inspired contrastive
formulation, we show that the Jensen-Shannon divergence underlying many
contrastive graph embedding models fails under disjoint positive and negative
distributions, which may naturally emerge during sampling in the contrastive
setting. In contrast, we demonstrate analytically that COLES essentially
minimizes a surrogate of Wasserstein distance, which is known to cope well
under disjoint distributions. Moreover, we show that the loss of COLES belongs
to the family of so-called block-contrastive losses, previously shown to be
superior compared to pair-wise losses typically used by contrastive methods. We
show on popular benchmarks/backbones that COLES offers favourable
accuracy/scalability compared to DeepWalk, GCN, Graph2Gauss, DGI and GRACE
baselines.
