Contrastive Laplacian Eigenmaps
Year: 2022

Abstract:
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 JensenShannon 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.

heading: 1 Introduction
text: Celebrated graph embedding methods, including Laplacian Eigenmaps [5] and IsoMap [42], reduce the dimensionality of the data by assuming that it lies on a low-dimensional manifold. The objective functions used in studies [5, 42] model the pairwise node similarity [7] by encouraging the embeddings of nodes to lie close in the embedding space if the nodes are closely related. In other words, such penalties do not guarantee that unrelated graph nodes are separated from each other in the embedding space. For instance, Elastic Embedding [8] uses data-driven affinities for the so-called local distance term and the data-independent repulsion term.
In contrast, modern graph embedding models, often unified under the Sampled Noise Contrastive Estimation (SampledNCE) framework [33, 28] and extended to graph learning [41, 15, 50], enjoy contrastive objectives. By maximizing the mutual information between patch representations and highlevel summaries of the graph, Deep Graph Infomax (DGI) [43] is a contrastive method. GraphSAGE [15] minimizes/maximizes distances between so-called positive/negative pairs, respectively. It relies on the inner product passed through the sigmoid non-linearity, which we argue below as suboptimal.
Thus, we propose a new COntrastive Laplacian EigenmapS (COLES) framework for unsupervised network embedding. COLES, derived from SampledNCE framework [33, 28], realizes the negative sampling strategy for Laplacian Eigenmaps. Our general objective is given as:
Θ∗ = argmax Θ Tr(fΘ(X) >∆WfΘ(X)) + βΩ(fΘ(X)). (1)
X ∈ Rn×d in Eq. (1) is the node feature matrix with d feature dimensions given n nodes, fΘ(X) ∈ Rn×d′ is an output of a chosen Graph Neural Network backbone (embeddings to optimize) with the
*The corresponding author. Code: https://github.com/allenhaozhu/COLES. 35th Conference on Neural Information Processing Systems (NeurIPS 2021).
feature dimension d′, Θ denotes network parameters, whereas ∆W ∈ Sn+ is the difference between the degree-normalized positive and negative adjacency matrices which represent the data graph and some negative graph capturing negative links for contrastive learning. Moreover, β ≥ 0 controls the regularization term Ω(·) whose role is to constrain the `2 norm of network outputs or encourage the so-called incoherence [36] between column vectors. Section 3.1 presents COLES for the Linear Graph Network (LGN) family, in which we take special interest due to their simplicity and agility.
By building upon previous studies [28, 2, 48], we show that COLES can be derived by reformulating SampledNCE into Wasserstein GAN using a GAN-inspired contrastive formulation. This result has a profound impact on the performance of COLES, as the standard contrastive approaches based on SampledNCE strategy (i.e., GraphSAGE [15]) turn out to utilize the Jensen-Shannon divergence, which yields log 2 constant and vanishing gradients for disjoint distributions of positive and negative sampled pairs used for contrastive learning. Figure 1 shows two examples of such nearly disjoint distributions. In contrast, COLES by design avoids the sigmoid in favour of the Radial Basis Function (RBF) non-linearity. We show that such a choice coincides with a surrogate of Wasserstein distance, which is known for its robustness under poor overlap of distributions, leading to the good performance of COLES. Moreover, we also show that the loss of COLES belongs to the family of so-called blockcontrastive losses, which were shown to be superior compared to pair-wise losses [3]. In summary, our contributions are threefold:
i. We derive COLES, a reformulation of the Laplacian Eigenmaps into a contrastive setting, based on the SampledNCE framework [33, 28].
ii. By using a formulation inspired by GAN, we show that COLES essentially minimizes a surrogate of Wasserstein distance, as opposed to the Jensen-Shannon (JS) divergence emerging in traditional contrastive learning. Specifically, by showing the Lipschitz continuous nature of our formulation, we prove that our formulation enjoys the Kantorovich-Rubinstein duality for the Wasserstein distance.
iii. We show COLES enjoys a block-contrastive loss known to outperform pair-wise losses [3].
Novelty. We propose a simple way to obtain contrastive parametric graph embeddings which works with numerous backbones. For instance, we obtain spectral graph embeddings by combining COLES with SGC [49] and S2GC [61], which is solved by the SVD decomposition.

heading: 2 Preliminaries
text: Notations. Let G=(V,E) be a simple, connected and undirected graph with n= |V | nodes and m= |E| edges. Let i ∈ {1, · · · , n} be the node index of G, and dj be the degree of node j of G. Let W be the adjacency matrix, and D be the diagonal matrix containing degrees of nodes. Moreover, let X ∈ Rn×d denote the node feature matrix where each node v is associated with a feature vector xv ∈ Rd. Let the normalized graph Laplacian matrix be defined as L = I−D−1/2ŴD−1/2 ∈ Sn+, a symmetric positive semi-definite matrix. Finally, scalars and vectors are denoted by lowercase regular and bold fonts, respectively. Matrices are denoted by uppercase bold fonts.

heading: 2.1 Negative Sampling
text: SampledNCE [14, 33, 28], a contrastive learning framework, is used by numerous works [41, 15, 50]. Let pd(u|v) and pn(u′|v) be the so-called data and negative distributions given the so-called anchor node v, where u and u′ denote the node for a positive and negative sample, respectively. Let pd(v) be the anchor distribution. Given some loss components sΘ(v, u) and s̃Θ(v, u′) whose role is to evaluate the similarity for pairs (v, u) and (v, u′), the contrastive loss is typically given as:
J(Θ) = Ev∼pd(v) [ Eu∼pd(u|v)sΘ(v, u) + ηEu′∼pn(u′|v)s̃Θ(v, u ′) ] , (2)
where η > 0 controls the impact of negative sampling. Let u ∈ Rd′ be the embedding of the node u obtained with an encoder fΘ(xu) given parameters Θ, where xu ∈ Rd is the initial node feature vector. Let u′ ∈ Rd′ and v ∈ Rd′ be embeddings of nodes u′ and v, accordingly. Let sΘ(u, v) = log σ(u
>v) and s̃Θ(u′, v) = log(1−σ(u′>v)), where σ(·) is the sigmoid function. Subsequently, one obtains the contrastive objective (to be maximized), employed by LINE [41], REFINE [60], GraphSAGE [15] and many other methods according to Yang et al. [50]:
J(Θ) = Ev∼pd(v) [ Eu∼pd(u|v) log σ(u >v) + ηEu′∼pn(u′|v) log σ(−u ′>v) ] . (3)
In what follows, we argue that the choice of sigmoid for σ(·) leads to negative consequences. Thus, we derive COLES under a different choice of sΘ(v, u) and s̃Θ(v, u′).

heading: 3 Methodology
text: In what follows, we depart from the above setting of (typical) contrastive sampling, which results in a derivation of our COntrastive Laplacian EigenmapS (COLES).

heading: 3.1 Contrastive Laplacian Eigenmaps
text: Instead of log-sigmoid used in sΘ(v, u) and s̃Θ(v, u′) of Eq. (3), let us substitute sΘ(v, u) = log exp(u>v) = u>v and s̃Θ(v, u′) = log exp(−u′>v) = −u′>v into Eq. (2), which yields:
J(Θ)=Ev∼pd(v) [ Eu∼pd(u|v)(u >v) + ηEu′∼pn(u′|v) ( −u′>v )] . (4)
We assume that variables of the above objective (to maximize) can be constrained (e.g., by the `2 norms to prevent ill-posed solutions) and represented by degree-normalized adjacency matrices. Next, we cast Eq. (4) into the objective of COLES (refer to our Suppl. Material for derivations):
Y∗ = argmin Y, s.t. Y>Y=I
Tr(Y>LY)− η ′
κ κ∑ k=1 Tr(Y>L (−) k Y)
= argmax Y, s.t. Y>Y=I
Tr(Y>∆WY) where ∆W=W(+) − η ′
κ κ∑ k=1 W (−) k ,
(5)
and the rows of matrix Y ∈ Rn×d′ contain the embedding vectors, L(−)k for k = 1, · · · , κ are randomly generated degree-normalized Laplacian matrices capturing the negative sampling, L(−)k = I−W(−)k and L=I−W(+). The scalar 0 ≤ η′ ≤ 1 ensures that L− η′ κ ∑η′ k=1 L (−) k ∈ Sn+ (one could truncate the negative spectrum instead) and controls the impact of W(−)k .
We note that COLES minimizes over the standard Laplacian Eigenmap while maximizing over the randomized Laplacian Eigenmap, which alleviates the lack of negative sampling in the original Laplacian Eigenmaps. However, unlike Laplacian Eigenmaps, we do not optimize over free variables Y but over the network parameters, as in Eq. (1) and (6). Clearly, if η′=0 and Y are free variables, Eq. (5) reduces to standard Laplacian Eigenmaps [5]: Y∗= argminY, s.t. Y>Y=I Tr(Y >LY).
COLES for Linear Graph Networks. In what follows, we are especially interested in the lightweight family of LGNs such as SGC [49] and S2GC [61] (APPNP [23] with the linear activation could be another choice) whose COLES-based objective can be reformulated as:
P∗ = argmax P, s.t. PP>=I Tr(PX>F>∆WFXP>). (6)
F ∈ Rn×n in Eq. (6) is the so-called spectral filter operating on the (degree-normalized) graph adjacency matrix, and P ∈ Rd′×d is a unitary projection matrix such that 0 < d′ < d. The solution to Eq. (6) can be readily obtained by solving the generalized eigenvalue problem X>F>∆WFXp = λp (an SVD on a small d × d matrix (X>F>∆WFX) ∈ Sd+). This step results in a matrix of embeddings fP(X) = FXP> ∈ Rn×d ′ for supervised training. Based on given a degree-normalized graph adjacency matrix W ∈ Rn×n, the spectral filters for SGC and S2GC are given as WK′ and αI + 1−αK′ ∑K′ k=1 W
k. Here, integer K ′ ≥ 1 and scalar α ≥ 0 are the number of layers and the importance of self-loop. Note that Eq. (6) is related to Locality Preserving Projections [17] if η′ = 0. Note also that enforcing the orthogonality constraints in Eq. (6) coincides with the SVD-based solution described above. In contrast, the more general form of COLES in Eq. (1) requires the regularization or constraints (depending on the backbone) imposed on minibatches i ∈ B e.g., we used the soft penalty Ω(fΘ(Xi))=‖f>Θ(Xi)fΘ(Xi)− I‖2F .
COLES (Stiefel). Inspired by the Locality Preserving Projections [17] and Eq. (6), we also investigate:
(P∗,Θ∗) = argmax P,Θ, s.t. PP>=I Tr(Pf>Θ(X)∆WfΘ(X)P >), (7)
solved on the Stiefel manifold by GeoTorch [29]. The embed. is: fP(X) = fΘ(X)P> ∈ Rn×d ′ .

heading: 4 Theoretical Analysis

heading: 4.1 COLES is Wasserstein-based Contrastive Learning
text: By casting the positive and negative distributions of SampledNCE as the real and generated data distributions of GAN, the key idea of this analysis is to (i) cast the traditional contrastive loss in Eq. (3) (used by LINE [41], GraphSAGE [15] and other methods [50]) as a GAN framework, and show this corresponds to the use of JS divergence and (ii) cast the objective of COLES in Eq. (4) as a GAN framework, and show it corresponds to the use of a surrogate of Wasserstein distance. The latter outcome is preferable under the vanishing overlap of two distributions, as the JS divergence yields log(2) constant and vanishing gradients. The Wasserstein distance suffer less from this issue.
For simplicity, consider the embedding v of the anchor node is given. An embedding vector u is sampled from the ‘real’ distribution pr(u) = pd(u | v), and u′ is sampled from the ‘generator’ distribution pg(u) = pn (u′ | v). Following Arjovsky et al. [2] and Weng [48], one arrives at a GAN-inspired formulation which depends on the choice of ‘discriminator’ D(u):
max Θ ∫ u ( pr(u) log(D(u)) + pg(u) log(1−D(u)) ) du ≤ 2JS (pr‖pg)− 2 log 2, (8)
where JS (pr‖pg) denotes the Jensen-Shannon (JS) divergence. If D(u) is completely free, then the optimal D∗(u) which maximizes the left-hand-side (LHS) of Eq. (8) is D(u) = pr(u)/(pr(u) + pg(u)). Plugging D∗ back into the LHS, we get the right-hand-side (RHS) of the inequality. In our setting, the case pg ∼ pr means that negative sampling yields hard negatives, that is, negative and positive samples are very similar. Hence, this family of embedding techniques try to optimally discriminate pr and pg in the embedding space.
The above analysis shows that traditional contrastive losses are bounded by the JS divergence. Regardless of the choice of D(u), if the support of the density pr and the support of pg are disjoint (e.g., positive and negative samples in the minibatch of the SGD optimization), the JS divergence yields zero and vanishing gradients. If the ‘discriminator’ is set to D(u) = σ(u>v), the objective in Eq. (8) becomes exactly Eq. (3). By noting ∂ log σ(u>v)/∂u = σ(u>v)v, the gradient is likely to vanish due to the scalar σ(u>v) and does not contribute to learning of network parameters. Figure 1 shows densities of x= u>v and x= u′>v for pr and pd estimated by the Parzen window on two sampled minibatches of contrastive GCN. Clearly, these distributions are approximately disjoint.
Compared with the JS divergence, the Wasserstein distance considers the metric structure of the embedding space:
inf γ∼Π(pr,pg)
E(u,u′)∼γ‖u− u′‖1, (9)
where Π(pr, pg) is the set of joint distributions with marginals pr(u) and pg(u′).
By the Kantorovich-Rubinstein duality [45], the optimal transport problem for COLES can be equivalently expressed as:
sup g:K(g)≤1
( Eu∼pr [g(u)]− Eu′∼pg [g(u′)] ) ≥ max
Θ
[ Eu∼pd(u|v)(u >v) + Eu′∼pn(u′|v)(−u ′>v) ] ,
(10)
under a drawn anchor v ∼ pd(v), where K(g) means the Lipschitz constant, and supreme is taken over all 1-Lipschitz functions (or equivalently, all K-Lipschitz functions.)
The “≥” is because g(u) is chosen to the specific form gv(u) = u>v, where v is parameterized by a graph neural network with parameters Θ. Optimizing over the neural network parameters Θ can enumerate a subset of functions which satisfies the Lipschitz constant K.
Lipschitz continuity of COLES. In order to assure the Lipschitz continuity of COLES, let individual embeddings be stacked row-wise into a matrix and `2-norm normalized along rows, or along columns. Given v (the reference node), the following holds:
|u>v − u′>v| ≤ ‖v‖max‖u− u′‖1,
where K = maxv ‖v‖max (≤ 1 in the case of either sphere embedding or the constraint Y>Y = I of the COLES formula in Eq. (5)). Thus, the function g(u) = u>v is Lipschitz with constant K.

heading: 4.2 COLES enjoys the Block-contrastive Loss
text: We notice that COLES leverages an access to blocks of similar data, rather than just individual pairs in the loss function. To this end, we resort to the Prop. 6.2 of Arora et al. [3], which shows that for family of functions F whose ‖f(·)‖ ≤ R for some R > 0, a block-contrastive loss Lblockun is always bounded by a pairwise-contrastive loss Lun , that is, Lblockun (f) ≤ Lun (f). To that end, Arora et al. [3] also show that as block-contrastive losses achieve lower minima than their pairwise-contrastive counterparts, they also enjoy better generalization.
We show that COLES is a block-contrastive loss, which explains its good performance. Following Eq. (4), for a given embedding v = fΘ(xv), and b embeddings ui = fΘ(xui) and u ′ i = fΘ(xu′i) drawn according to pd(u | v) and pn(u′ | v), we have (note minus preceding eq. as here we minimize):
−Eu∼pd(u|v)(u >v)+Eu′∼pn(u′|v)
( −u′>v ) = −v> (∑ i ui b − ∑ i u ′ i b′ ) = −v>(µ+−µ−), (11)
where µ+ and µ− are positive and negative block summaries of sampled nodes. Looking at Eq. (5), it is straightforward to simply expand ∑ (i,j)∈E ‖yi − yj‖22 ∆Wij to see that each index i will act as a selector of anchors, whereas index j will loop over positive and negative samples taking into account their connectivity to i captured by ∆Wij . We provide this expansion in the Suppl. Material.

heading: 4.3 Geometric Interpretation.
text: Below, we analyze COLES through the lens of Alignment and Uniformity on the Hypersphere of Wang and Isola [47]. To this end, we decompose our objective into the so-called alignment and uniformity losses. Firstly, Mikolov et al. [33] have shown that SampledNCE with the sigmoid non-linearity is a practical approximation of SoftMax contrastive loss, the latter suffering poor scalability w.r.t. the count of negative samples. For this reason, many contrastive approaches (DeepWalk, GraphSAGE, DGI, Graph2Gauss, etc.) adopt SampledNCE rather than SoftMax (GRACE) framework.
Wang and Isola [47] have decomposed the SoftMax contrastive loss into Lalign and Lumiform [47]:
L(u, v,N ) = Lalign(u, v) + Luniform(u′, v,N ) = − log eu
>v eu>v + ∑
u′∈N e u′>v
(12)
where N is a sampled subset of negative samples, u and v are node indexes of so-called positive sample and anchor embeddings, u and v. Let 〈u,u〉 = 〈u′,u′〉 = 〈v,v〉 = τ2(τ acts as the so-called temperature). Moreover, Lalign = −〈u,v〉 and Luniform = log ∑ u‡∈N∪{u} e u‡ > v, that is, Luniform is
a logarithm of an arithmetic mean of RBF responses over the subset N ∪ {u}. Of course, computing the total loss L requires drawing u and v from the graph and summing over multiple Lalign(u, v) and L′uniform(u, v,N ) but we skip this step and the argument variables of loss functions for brevity. COLES can be decomposed into Lalign and Lumiform [47] as follows:
Lalign + L′uniform = − log eu >v − 1 |N | ∑ u′∈N log e−u ′>v = − log e u>v( Πu′∈N eu ′>v ) 1 |N| , (13)
where Lalign remains the same with SoftMax but L′uniform = log ( Πu′∈N e u′>v ) 1 |N| is in fact a logarithm of the geometric mean of RBF responses over the subset N . Thus, our loss can be seen as the ratio of geometric means over RBF functions. Several authors (e.g., Gonzalez [12]) noted that the geometric mean helps smooth out the Gaussian noise under the i.i.d. uniform sampling while loosing less information than the arithmetic mean. The geometric mean enjoys better confidence intervals the arithmetic mean given a small number of samples. As we sample few negative nodes for efficacy, we expect the geometric mean is more reliable. Eq. (12) and (13) are just two specific cases of a generalized loss:
Lalign + L′′uniform = − log eu
>v
Mp
( eu ′ 1 >v, · · · , eu ′> |N|v ) , (14) where Mp(·) in L′′uniform = logMp ( eu ′ 1 >v, · · · , eu ′> |N|v ) is the so-called generalized mean. We
introduce Mp(·) into the denominator of Eq. (14) but it can be also introduced in the numerator. We investigate the geometric (p=0), arithmetic (p=1), harmonic (p=−1) and quadratic (p=2) means.

heading: 5 Related Works
text: Graph Embeddings. Graph embedding methods such as Laplacian Eigenmaps [5] and IsoMap [42] reduce the dimensionality of representations by assuming the data lies on a low-dimensional manifold. With these methods, for a set of high-dimensional data features, a similarity graph is built based on the pairwise feature similarity, and each node embedded into a low-dimensional space. The graph is constructed from non-relational high dimensional data features, and Laplacian Eigenmaps ignore relations between dissimilar node pairs, that is, embeddings of dissimilar nodes are not penalized.
To alleviate the above shortcomings, DeepWalk [35] uses truncated random walks to explore the network structure and utilizes the skip-gram model [32] for word embedding to derive the embedding vectors of nodes. LINE [41] explores a similar idea with an explicit objective function by setting the walk length as one and applying negative sampling [32]. Node2Vec [13] interpolates between breadth- and depth-first sampling strategies to aggregate different types of neighborhoods.
Representation Learning for Graph Neural Networks. Supervised and (semi-)supervised GNNs [22] require labeled datasets that may not be readily available. Yet, unsupervised GNNs have received little attention. GCN [22] employs the minimization of reconstruction error as the objective function to train the encoder. GraphSAGE [15] incorporates objectives inspired by DeepWalk e.g., contrastive loss encouraging nearby nodes to have similar representations while preserving dissimilarity between representations of disparate nodes. DGI [44], inspired by Deep InfoMax (DIM) [18], proposes an objective with global-local sampling strategy, which maximizes the Mutual Information (MI) between global and local graph embeddings. In contrast, Augmented Multiscale Deep InfoMax (AMDIM) [4] maximizes MI between multiple views of data. MVRLG [16] contrasts encodings from first-order neighbors and a graph diffusion. MVRLG uses GCNs to learn node embeddings for different views. Fisher-Bures Adversary GCN [40] assumes that the graph is generated w.r.t. some observation noise. Graph-adaptive ReLU [58] uses an adaptive non-linearity in GCN. Multi-view augmentation-based methods, not studied by us, are complementary to COLES. Moreover, linear networks e.g., SGC [49] and S2GC [61] capture the neighborhood and increasingly larger neighborhoods of each node, respectively. SGC and S2GC have no projection layer, which results in embeddings of size equal to the input dimension. DGI [44] uses the block-contrastive strategy [3] by treating negative samples as a difference of instances and a summary of node embeddings for positive samples. Finally, COLES can be extended to other domains/problems e.g., time series/change point detection [9] or few-shot learning [39, 54, 55]. (Negative) Sampling. Sampling node pairs relies on random walks [35] or second-order proximity [41], etc. In contrast, COLES samples an undirected graph based on the random graph sampling theory [11], where each edge is independently chosen with a prescribed probability p′ > 0.

heading: 6 Experiments
text: We evaluate COLES on transductive and inductive node classification tasks. Node clustering is also evaluated. COLES is compared to state-of-the-art unsupervised, contrastive and (semi-)supervised methods. Unsupervised methods do not use label information except for the classifier. Contrastive methods use the contrastive setting to learn similarity/dissimilarity. (Semi-)supervised methods use labels to train their projection layer and classifier. By semi-supervised, we mean that only a few of nodes used for training are labeled. (Semi-)supervised models use a SoftMax classifier, whereas unsupervised and contrastive methods use a logistic regression classifier.
Datasets. COLES is evaluated on four citation networks: Cora, Citeseer, Pubmed, Cora Full [22, 6] for transductive setting. We also employ the large scale Ogbn-arxiv from OGB [19]. Finally, the Reddit [53] dataset is used in inductive setting. Table 1 provides details of all datasets.
Metrics. Fixed data splits [51] for transductive tasks are often used in evaluations between different models. However, such an experimental setup may benefit easily overfitting models [38]. Thus, instead of fixed data splits, results are averaged over 50 random splits for each dataset and standard deviations are reported for empirical evaluation on transductive tasks. Moreover, we also test the performance under a different number of samples per class i.e., 5 and 20 samples per class. Typically, the performance for the inductive task is tested on relatively larger graphs. Thus, we choose fixed data splits as in previous papers [15, 53], and we report the Micro-F1 scores averaged on 10 runs.
Baseline models. We group baseline models into unsupervised, contrastive and (semi-)supervised methods, and implement them in the same framework/testbed. Contrastive methods include DeepWalk [35], GCN+SampledNCE developed as an alternative to GraphSAGE+SampledNCE [15], Graph2Gauss [6], SCE [56], DGI [44], GRACE [62], GCA [63] and GraphCL [52], which are our main competitors. Note that GRACE, GCA and GraphCL are based on multi-view and data augmentation, and GraphCL is mainly intended for graph classification. We do not study graph classification as it requires advanced node pooling [24] with mixed- or high-order statistics [26, 25, 27]. We compare results with representative (semi-)supervised GCN [22], GAT [44] and MixHop [1] models. SGC and S2GC are unsupervised spectral filter networks. They do not have any learnable parameters that depend on labels, with exception of a classifier. To reduce the resulting dimensionality, we also add PCA-S2GC and RP-S2GC, which use PCA and random projections to obtain the projection layer on these methods. We extend our COLES framework with different GNNs: GCN, SGC and/or S2GC, and we name them COLES-GCN, COLES-SGC and COLES-S2GC. As COLES-GCN is a multi-layer non-linear encoder, the optimization of COLES-GCN is non-convex. The optimization of COLES-SGC and COLES-S2GC is convex if L− η ′
κ ∑η′ k=1 L (−) k ∈ Sn+, and COLES-GCN (Stiefel) is
convex w.r.t. P. We set hyperparameters based on the settings described in their papers.
General model setup. For all (semi-)supervised models, we use early stopping on each random split and we capture the corresponding classification result. For all unsupervised models, we choose the embedding dimension to be 512 on Cora, Citeseer and Cora Full, and 256 on Pubmed. After the embeddings of nodes are learnt, a classifier is trained by applying the logistic regression in the embedding space. For inductive learning, methods based on COLES use 512-dimensional embeddings. Other hyperparameters for the baseline models are the same as in original papers.
Hyperparameter of our models. In the transductive experiments, the detailed hyperparameter settings for Cora, Citeseer, Pubmed, and Cora Full are listed below. For COLES, we use the Adam optimizer with learning rates of [0.001, 0.0001, 0.02, 0.02] and the decay of [5e−4, 1e−3, 5e−4, 2e−4]. The number of training epochs are [20, 20, 100, 30], respectively. We sample 10 randomized adjacent matrices, and 5 negative samples for each node in each matrix on each dataset before training. For the S2GC and COLES-S2GC, the number of propagation steps (layers) are 8 for all datasets except Cora Full (2 steps). For SGC and COLES-SGC, we use 2 steps for all datasets.

heading: 6.1 Transductive Learning
text: In this section, we consider transductive learning where all nodes are available in the training process.
Contrastive Embedding Baselines vs. COLES. Table 2 shows that the performance of COLESGCN and the linear variant, COLES-S2GC, are better than other unsupervised models. In particular, COLES-GCN outperforms GCN+SampledNCE on all four datasets, which shows that COLES has an advantage over the SampledNCE framework. In addition, COLES-S2GC typically outperforms the
best contrastive baseline DGI by up to 3.4%. In Cora Full, we notice that S2GC underperforms when training with 5 samples. However, COLES-S2GC is able to significantly boost its performance by 9%. On Citeseer with 5 training samples, COLES-S2GC outperforms S2GC by 6.8%. We also note that COLES-GCN (Stiefel) outperforms COLES-GCN (based on the soft-orthogonality constraint) by up to 2.7% but its performance below the performance of COLES-S2GC.
Noteworthy is that for augmentation-based methods, COLES-GCN with augmentations denoted as COLES-GCN (+Aug) outperforms COLES-GCN without augmentations. COLES-GCN (+Aug) also outperforms GRACE and GCA, and GraphCL in most experiments. Nonetheless, COLES-S2GC without any augmentations outperformed all augmentation-based methods.
Finally, Table 7 shows that COLES-S2GC outperforms all other methods on the challenging Ogbnarxiv, while using a very small number of trainable parameters.
Semi-supervised GNNs vs. COLES. Table 2 shows that the contrastive GCN baselines perform worse than semi-supervised variants, especially when 20 labeled samples per class are available. In contrast, COLES-GCN outperformed the semi-supervised GCN on Cora by 6.3% and 1.4% given 5 and 20 labeled samples per class. COLES-GCN also outperforms GCN on Citeseer and Cora Full by 8.3% and 6.3% given 5 labeled samples per class. When the number of labels per class is 5, COLES-S2GC outperforms GCN by a margin of 8.1% on Cora and 9.4% on Citeseer. These results show the superiority of COLES on four datasets when the number of samples per class is 5. Even for 20 labeled samples per class, COLES-S2GC outperforms the best semi-supervised baselines on all four datasets e.g., by 1.7% on Citeseer. Semi-supervised models are affected by the low number of labeled samples, which is consistent with [31], e.g., for GAT and MixHop. The accuracy of COLES-GCN and COLES-S2GC is not affected as significantly due to the contrastive setting.
Unsupervised GNNs vs. COLES. SGC and S2GC are unsupervised LGNs as they are spectral filters which do not use labels (except for the classifier). Table 2 shows that COLES-S2GC outperforms RP-S2GC and PCA-S2GC under the same size of projections. In most cases, COLES-S2GC also outperforms the unsupervised S2GC baseline (high-dimensional representation).
Negative Laplacian Eigenmaps. Below, we analyze how κ in Eq. (5) influences the performance. We set κ ∈ {0, 1, 5, 10} on COLES-S2GC and COLES-GCN given Cora and Citeseer with 5 and 20 labeled samples per class. The case of κ=0 means no negative Laplacian Eigenmaps are used, thus the solution simplifies to regular Laplacian Eigenmaps parametrized by GCN embeddings. Table 3 shows that without the negative Laplacian Eigenmaps, the performance of COLES-S2GC drops significantly i.e., between 6% and 9% for 5 labeled samples per class. That means the negative Laplacian Eigenmaps play important role which highlights the benefits of COLES. Although negative Laplacian Eigenmaps improve results, using κ>1 negative matrices improves the performance only marginally. Table 4 shows that COLES-GCN relies on negative Laplacian Eigenmaps. Without negative Laplacian Eigenmaps, the performance of COLES-GCN drops by 20% on Citeseer with 5 samples per class. Even when 20 samples per class are used, if κ = 0, the performance of COLES-GCN drops by 8.4%.
6.2 Uniformity Loss as the Generalized Mean (Mp).
Following the analysis presented in Section 4.3, Table 5 demonstrates the impact of the choices of the uniformity loss on the performance of COLES. To this end, we select the geometric (M0), arithmetic (M1), harmonic (M−1) and quadratic(M2) means as examples of Mp realizing the uniformity loss. On all the investigated datasets, the geometric mean outperforms other variants.

heading: 6.3 Inductive Learning
text: In inductive learning, models have no access to the test set, thus they need to generalize well to unseen samples. Table 6 shows that COLES enjoys a significant performance gain (1% - 5% in Micro-F1 scores), performing close to supervised methods with a low memory footprint. In contrast, DGI on Reddit triggers out-of-memory errors on Nvidia GTX 1080 GPU (94.0 Micro-F1 is taken from [44]).

heading: 6.4 Node Clustering
text: We compare COLES-GCN and COLES-S2GC with three types of clustering methods listed below: i. Methods that use only node features e.g., k-means and spectral clustering (spectral-f) construct a
similarity matrix with the node features by a linear kernel.
ii. Structural clustering methods that only use the graph structure: spectral clustering (spectral-g) that takes the graph adjacency matrix as the similarity matrix, and DeepWalk [35].
iii. Attributed graph clustering methods that use node features and the graph: Graph Autoencoder (GAE), Graph Variational Autoencoder (VGAE) [22], Adversarially Regularized Graph Autoencoder (ARGE), Variational Graph Autoencoder (ARVGE) [34], SGC [49] and S2GC [61].
We measure the performance by the clustering Accuracy (Acc), Normalized Mutual Information (NMI) and macro F1-score (F1). We run each method 10 times on Cora, CiteSeer and PubMed. We report the clustering results in Table 8. We set the number of propagation steps to 8 for SGC, S2GC, COLES-SGC and COLES-S2GC, following the setting of [57]. We note that COLES-S2GC outperforms S2GC in most cases, whereas COLES-GCN outperforms contrastive GCN on all datasets.
Scalability. GraphSAGE and DGI require neighbor sampling which result in redundant forward/backward propagation steps (long runtime). In contrast, COLES-S2GC enjoys a straightforward implementation which reduces the memory usage and runtime significantly. For graphs with more than 100 thousands nodes and 10 millions edges (Reddit), our model runs smoothly on NVIDIA 1080 GPU. Even on larger graph datasets, the closed-form solution is attractive as for COLES-S2GC, the cost of eigen-decomposition depends on d (a few of seconds on Reddit). The runtime of COLESS2GC is also favourable in comparison to multi-view augmentation-based GraphCL. Specifically, COLES-S2GC took 0.3s, 1.4s, 7.3s and 16.4s on Cora, Citeseer, Pubmed and Cora Full, respectively. GraphCL took 110.19s, 101.0s, ≥ 8h and ≥ 8h respectively.

heading: 7 Conclusions
text: We have proposed a new network embedding, COnstrative Laplacian EigenmapS (COLES), which recognizes the importance of negative sample pairs in Laplacian Eignemaps. Our COLES works well with many backbones, e.g., COLES with GCN, SGC and S2GC backbones outperforms many unsupervised, contrastive and (semi-)supervised methods. By applying the GAN-inspired analysis, we have shown that SampledNCE with the sigmoid non-linearity yields the JS divergence. However, COLES uses the RBF non-linearity, which results in the Kantorovich-Rubinstein duality; COLES essentially minimizes a surrogate of Wasserstein distance, which offers a reasonable transportation plan, and helps avoid pitfalls of the JS divergence. Moreover, COLES takes advantage of the so-called block-contrastive loss whose family is known to perform better than their pair-wise contrastive counterparts. Cast as the alignment and uniformity losses, COLES enjoys the more robust geometric mean rather than the arithmetic mean (used by SoftMax-Contrastive) as the uniformity loss.
Acknowledgments and Disclosure of Funding
We would like to thank the reviewers for stimulating questions that helped us improve several aspects of our analysis. Hao Zhu is supported by an Australian Government Research Training Program (RTP) Scholarship. Ke Sun and Piotr Koniusz are supported by CSIRO’s Machine Learning and Artificial Intelligence Future Science Platform (MLAI FSP).

Review summaries:
In this work, the authors improved contrastive learning of graph node embedding from the viewpoint of Laplacian eigenmap. Removing nonlinear activation used in traditional NCE, the authors reformulate NCE as a randomized Laplacian eigenmap problem, which can be used to learn the GNNs with linear architectures. The authors claimed that the proposed method is equivalent to minimize the expectation of the Wasserstein distance between the positive and the negative distributions conditioned on the target node.   -- after rebuttal --- Most of my concerns are solved, so I change my score from 5 to 6.

This paper provides a reformulation of the traditional Laplacian Eigenmaps in a contrastive setting, for graph nodes embedding. Theoretical results for its connection to Wasserstein distance and block-contrastive loss are presented. Overall, I think this is a good paper with substantial contributions in connecting manifold learning and constructive learning. 

The paper proposes a reformulation of Laplacian Eigenmaps in a log-linear contrastive setting. Inspired by GAN architecture, the authors show that the their contrastive laplacian eigenmaps (COLES) minimises a surrogate of Wasserstein distance as opposed to JS distance in traditional contrastive methods. Further, COLES in shown to enjoy block contrastive loss, which is upper bounded by pair-wise loss.   The authors show that the log-linear contrastive loss can be reformulated as a generalised eigenvalue (GEV) problem of a contrastive degree normalised adjacency matrix. They apply this formulation to line graph networks such as SGC and $S^{2}$GC and obtain a closed form solution to the matrix of node embeddings, which depends on a spectral filter and the solution to the GEV problem.   By casting the positive and negative samples as the real and generated data from a GAN, the authors show that traditional contrastive losses can be reformulated into JS divergence, while COLES can be cast into a surrogate of 1-Wasserstein  metric. They claim that the latter is preferable since, under poor overlap of the the two distributions JS divergence vanishes, leading to vanishing gradients, while 1-Wasserstein distance does not.   The authors also show that COLES is Lipschitz continuous and enjoys block contrastive loss, wherein one can leverage blocks of similar data as opposed individual pairs. Since from [Saunshi et al] block contrastive loss is smaller than pair-wise loss, the authors claim that COLES is expected to achieve a lower minimum.   The authors perform empirical evaluation on a host of open source datasets and multiple baseline backbones. In most tasks, COLES objective seems to outperform the methods included in the comparison.