Contrastive Laplacian Eigenmaps
Authors: Hao Zhu
Ke Sun
Piotr Koniusz
Venue: NeurIPS 2021 Poster (2021)
Keywords: Laplacian Eigenmaps
Graph Neural Networks
Contrastive Learning
Wassertein Distance
Kantorovich-Rubinstein duality
Block-Contrastive
Geometric Mean

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 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.

Contrastive Laplacian Eigenmaps
Hao Zhut
Ke Sun
Piotr Koniusz *&8.f
DCta61/CSIRO Australiia National University
allenhaozhu@ gomal sunk @ ieee.org, piotr.koniusz @ data61 ccsiro..
Abstract
Graph contrastive learning attracts/disperses node representations for similar/dis- similar 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 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, 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 analyt- ically 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 so-called block-contrastive losses, previously shown be superior compared pair-wise losses typically used by contrastive methods. We show on popular senchnarks/backbook that COLES offers favourable accuracy/scalability compared to BeepWalk, GCN, Graph2Gauss, DGI and GRACE baselines.
1 Introduction
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] 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 guarantee that unrelated graph nodes are separated from each other the embedding space. For instance, Elastic Embedding [8] uses data-driven affinities for the so-called local distance term and the cate-inndeenneett repulsion term.
In contrast, modern graph embedding models, often unified under the Sampled Noise Contrastive Estimation (SampledNCE) framework [33, 28] and extended graph learning [41, 15, 50], enjoy contrastive objectives. By maximizing the mutual information between patch representations and high- level summaries of the graph, Deep Graph Infomax (DGI) [43] is a contrastive method. GraphS distances between so-called positive/negative pairs, respectively. It relies
[15] minimizes/maxinee on the inner product passed through the sigmoid non- -on-eiiea,,,y, which we argue below as suboptimal.
Thus, propose COntrastive Laplacian EigenmapS (COLES) framework for unsuper- vised network embedding. COLES, derived from SampledNCE framework [33, 28], realizes the negative sampling strategy for Laplacian Eigenmaps. Our general objective is given as:
arg max
AW (e + (a(fe(())))
(1)
X E R Eq. (1) the node feature matrix with feature dimensions given n nodes, fe( E Ignxd' is an output of chosen Graph Neural Network backbone (embeddings to optimize) with the
'The corresponding author.
Code: https://github. com. httpecchw...oalaaaaanaaeeeeeeeee wwlaaeaaoehuc/ll.....
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

xwxuuva secuun _
x <u.v> y=
density
density
0.4
0.3
4
0.2
2
%0.4
-0.2
0.0
0.2
0.4
0.0
15
inner product
Inner product (x)
(a)
(b)
Figure 1: Densities of dot-product scores (v, u) and (v. u²) (red and blue curves) between the anchor/positive embedding and the anchor/negative embedding (GCN contrastive setting). Left/right figures use two distinct minibatches sampled on Cora. With the small overlap of distributions, many contrastive methods relying the JS divergence may underperform (see Section 4.1 for details).
feature dimension d', O denotes network parameters, whereas AW& E S4 is the difference between the Regrre-normaalin positive and negative adjacency matrices which represent the data graph and some negative graph capturing negative links for contrastive learning. Moreover, 3 2 0 controls the regularization term ()-) whose role is to constrain the Eg norm of network outputs or encourage the so-called incoherence [36] between column vectors. Section 3. presents COLES for the Linear Graph Network (L.GN) 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 GAN-inspired contrastive formulation. This result has profound impact on the performance of COLES, as the standard contrastive approaches based on SampledNCE strategy (i.e., GraphSAGE (15]) turn out 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 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 block- contrastive losses, which were shown to be superior compared to pair-wise losses [3]. In summary, our contributions are threefold:
We derive COLES, a reformulation of the Laplacian Eigenmaps into a contrastive setting, based the SampledNCE framework [33, 28].
ii. By using formulation inspired by GAN, we show that COLES essentially minimizes a surrogate of Wasserstein distance, as opposed the Jensen-Shannon (JS) divergence emerging traditional contrastive learning. Specifically, by showing the Lipschitz continuous nature of our formulation, we prove that our formulation enjoys the Kantorovich-Rubing Rubinstein duality for the Wasserstein distance.
iii. We show COLES enjoys a block-contrasiive loss known to outperform pair-wise losses [3].
Novelty. We propose simple way obtain contrastive parametric graph embeddings which works with numerous backbones. For instance, we obtain spectral graph embeddings by combining COLES with SGC [49] and S²GC [61], which solved by the SVD decomposition.
2 Preliminaries
Notations. G= E) be a simple, connected and undirected graph with n n= [V nodes and m= |E| edges. Let f1.... n be the node index of G, and d, 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 Raad denote the node feature matrix where each node v is associated with a feature vector x, E R Let the normalized graph Laplacian matrix be defined as L = I - D D 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.
E S

---

2.1 Negative Sampling
SampledNCE [14, 33, 28]. a contrastive learning framework, is used by numerous works [41, 15, 50]. Let pa(u/z) and pv. (a' (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 positive and negative sample, respectively. Let pa(u) be the anchor distribution. Given some loss components se (v, u) and se w') whose role is to evaluate the similarity for pairs (v, u) and (v, v'), the contrastive loss typically given as:
I( = Rowpptt) [Eunrpatllu) (v. u) (1r))
where 7) > controls the impact of negative sampling, Let E Rdd be the embedding of the node u obtained with an encoder (x.) given parameters O where X Rd the initial node feature vector. Let u' E Rdd and v E IR be embeddings of nodes u' and e, accordingly. Let se (u, v) log ar v) and ( v) log(1-o(u') v)), where a(-) 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]:
((+) Eowpp(() [Burpa(alls) log o( v) + 7)Eu'pp(('(l)) log logo(-"' v)]
(3)
In what follows, we argue that the choice of sigmoid for o(-) leads negative consequences. Thus, we derive COLES under different choice of se (v, u) and se (w, w').
3 Methodology
In what follows, we depart from the above setting of (typical) contrastive sampling, which results in derivation our COntrastive Laplacian EigenmapS (COLES).
3.1 Contrastive Laplacian Eigenmaps
Instead of log- sigmoid used in ses u) and s (v, u') ) of Eq. (3), let us substitute s u) = log exp(u T v) = u T v and (w, u') = log exp( ( u = -u' T' into Eq. (2), which yields:
J(O) = Eurpp(tt) [Tuu-patul]]] (u v) + (M (-u'Tv)]
(4)
We assume that variables of the above objective (to maximize) can be constrained (e.g., by the B2 norms to prevent ill-posed solutions) and represented by degree-normalize adjacency matrices. Next, cast Eq. (4) into the objective of COLES (refer
Suppl. Material for derivations):
T Tr
Y = arg min
Tr LY) Y.
K
(5)
arg max T(YTAWY) Y,st YTY=I
where
AW=W(+) 7
( k
and the rows of matrix Y E Raxd contain the embedding vectors, L for k 1, ... H are randomly generated degree-normalized Laplacian matrices capturing the negative sampling. k
I-W(-) and L (++),, The scalar 0 < n' < 1 ensures that L z' Σ k== L(-) S (one could truncate the negative spectrum instead) and controls the impact of w
We note that COLES minimizes over the standard Laplacian Higenmap while maximizing over the randomized Laplacian Figenmap, which alleviates the lack of negative sampling in the original Laplacian Eigenmaps. However, unlike Laplacian Eigenmaps, we do not optimize over free variables but over the network parameters, as in Eq. (1) and (6). Clearly, if r/' =0 0 and Y are free variables, Eq. (5) reduces to standard Laplacian Eigenmaps [5]: Y arg milly Y- Tr(Y LYY.
COLES for Linear Graph Networks. In what follows. we are especially interested in the lightweight family of LGNs such as SGC [49] and S'GC [61] (APPNP [23] with the linear activation could be another choice) whose COLES COLES-based objective can be reformulated as:
P
arg TrPP T AWFXPP
(6)
st PPT =I
3

---

F E R in Eq. (6) is the so-called spectral filter operating on the (degree- normalized) graph adjacency matrix, and P E IRd xd is unitary projection matrix such that 0 < d' < d. The solution to Eq. (6) can be readily obtained by solving the generalized eigenvalue problem
APXp (XFF F FWFF) E $ This step results in matrix of
Ap (an SVD on small d x d matrix (X embeddings (x( FXPT E Ruadd for supervised training. Based on given a degree-normaalized graph adjacency matrix W E Ruxn the spectral filters for SGC and SCGC are given as W and al + - Σx= W Here, integer K' 2 1 and scalar 2 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 E e.g., we used the soft penalty (X))) II (X))
COLES (Stiefel). Inspired by the Locality Preserving Projections [17] and Eq. (6), we also investigate:
(P* -²) arg
P.e. PP
solved on the Stiefel manifold by GeoTorch [29]. The embed. is: fp(X) = fx E Baxd
4 Theoretical Analysis
4.1 COLES is Wasserstein- Contrastive Learning
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 l2g(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 p-(u) Pa(u v), and u' is sampled from the 'generator' distribution pz(u) = Ps. (u' v). Following Arjovsky et al. [2] and Weng [48], one arrives at GAN-inspired formulation which depends on the choice of 'discriminator" D(u):
max /. (pr (u) (og((())) + P, log(1 D(u)) du S 2JS (pr lp,)) - 2 log 2,
(8)
where JS (p- (pg) denotes the Jensen-Shannee Shannon (JS) divergence. If D(u) is completely free, then the optimal D' (u) which maximizes the seft-han-ssie (LHS) of Eq. (8) is D(u) pr (u)/(p, (u) + (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 Py in the embedding space.
The above analysis shows that traditional contrastive losses are bounded by the JS divergence. Regardless of the choice of Duu), if the support of the density p, and the support of py 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) = o(u 'v). the objective in Eq. (8) becomes exactly Eq. (3). By noting 2 log a a( T Tv)/n = au v)v, the gradient is likely to vanish due to the scalar (u v) and does not contribute to learning of network parameters. Figure I shows densities of x sampled minibatches of contrastive GCN. Clearly, these distributions are approximately disjoint.
and x TTTv for p. and pa estimated by the Parzen window on two
Compared with the JS divergence, the Wasserstein distance considers the metric structure of the embedding space:
inf T-
Th Ey I u' ||:
(9)
where 11(pr. Pg) is the set of joint distributions with marginals (u) and pa (u').

---

By the Kantorovich- duality [45]. the optimal transport problem for COLES can be equivalently expressed as:
sup (Euxp. (g(u) - l (g o: K(9)
(10)
max E (umpallll) [v) + (w
under drawn anchor pa(u), where (g) means the Lipschitz constant, and supreme is taken over all 1-I.ipschitz. functions (or equivalently, all K K-Liisshitz functions.)
The "2" because (uu) is chosen to the specific form (u) = u v, where v is parameterized by 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- fg-norm normalized along rows, or along columns. Given (the reference node), the following holds:
Iu v u'vl ||v/||mx u' ||
where K = max, || (S in the case of either sphere embedding or the constraint Y Y of the COLES formula in Eq. (5)). Thus, the function g(u) = u Lipschitz with constant K.
4.2 COLES enjoys the Block-contrastive Loss
We notice that COLES leverages 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 J whose [I] < R for some R >> block-contrastive loss L. Lbblck is always bounded by pairvise-contrastiee loss Lun that is, 7, block (J") S Lum (f). To that end, Arora et al. Jun [3] also show that block-comtrastive losses achieve lower minima than their pairwise-contrastive counterparts, they also enjoy better generalization.
We show that COLES is block-contrastive loss, which explains its good performance. Following Eq. (4), for a given embedding v = fx(x)), and b embeddings u, = -fe -f,()u,) and u fe (x.:) drawn according to Pa(u v) and Pr,(u) v), we have (note minus preceding eq. as here we minimize):
Eu-pa(ulo) V (-u' Vv = -v Σ カーーール ) -
--), -
E,
(11)
where fxt and μ are positive and negative block summaries of sampled nodes. Looking at Eq. (5), it is straightforward simply expand Σ(.)ER lly; - ,1, AW;, to see that each index i will act selector of anchors, whereas index j will loop over positive and negative samples taking into account their connectivity to captured by AWi.. We provide this expansion in the Suppl. Material.
4.3 Geometric Interpretation.
Below, analyze COLES through the lens of Alignment and Uniformity the Hypersphere of Wang and Isola [47]. To this end, we decompose our objective into the so-called alignment and uniformity losses. Firstly, Mikolov al. [33] have shown that SampledNCE with the sigmoid non-line -ineariyyy is practical approximation of SoftMax contrastive loss, the latter suffering poor scalability w.r.. 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 Latign and Lumifom [47]:
C(u, N) Latign (u, v) Luniforn v,,) - -log e Evex
(12)
where N' is a sampled subset of negative samples, and v are node indexes of so-called positive sample and anchor embeddings, and v. Let (u, u) (u', u') (v, 7²(r acts the so-called
temperature). Moreover, Lalign =uu v)) and Luniform log EnteNu(n) e"² that is, Lunifoem is
5

---

a logarithm of an arithmetic mean of RBF responses over the subset U {u). Of course, computing the total loss L requires drawing and from the graph and summing over multiple Laiggn (u, v) and f'unitorm (u, V) but we skip this step and the argument variables of loss functions for brevity.
COLES can be decomposed into Latign and Lumiform [47]
follows:
en
Latign + f'mitoom log e 'v
loge nn'v
log
(13)
(Iw' ViT VIATT
W'EN
where Calign remains the same with SoftMax but C'uifoom log (IwENe" Dh
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 small number of samples. As 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:
cu'v
Latign + umiform log
(14)
Mp (cui v )
where M,(-) in Cimitom log Mp (e"i ,.. .e..,eein e"(xrv) is the so-called generalized mean. We introduce M-)-) into the denominator of Eq. (14) but it can be also introduced in the numerator. We
investigate the geometric (p= arithmetic (p=1), 1), harmonic (1=-1) and quadratic (p=2) 2) means.
5 Related Works
Graph Embeddings. Graph embedding methods such Laplacian Eigenmaps [5] and IsoMap [42] reduce the dimensionality of representations by assuming the data lies on low-dimensional manifold. With these methods, for a set of high-dimensionall data features, similarity graph is built based on the pairwise feature similarity, and each node embedded into a now-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 shorteomings, DeepWalk [35] uses truncated random walks explore the network structure and utilizes the skip-gram model [32] for word embedding to derive the embedding
vectors of nodes. LINE [41] explores 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.
Learning for Graph Neural Networks. Supervised and (semi- yupprrisue 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 Deep- Walk 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 em- beddings for different views. Burberr-Brrss/ee Adversary GCN [40] assumes that the graph is generated w.r.t. some observation noise. Graph-adaptive ReLU [58] uses 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 SC [61] capture the neighborhood and increasingly larger neighborhoods of each node, respectively. SGC and SCGC have no projection layer, which results in embeddings of size equal to the input dimension. DGI [44] uses the conkkcoontasttive 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].
Representation
(Negative) Sampling. Sampling node pairs relies on random walks [35] or second-orden proximity [41], etc. In contrast, COLES samples an undirected graph based the random graph sampling theory [11], where each edge is independently chosen with a prescribed probability p' > 0.

---

6 Experiments
We evaluate COLES on transductive and inductive node classification tasks. Node clustering is also evaluated. COLES is compared to state-of- of-t-ooftthearr art unsupervised, contrastive and Sepeerisuee methods. Unsupervised methods do not use label information except for the classifier. Contrastive methods use the contrastive setting to learn similarityddssimilarryy (Semi-)superrisie
methods use labels to train their projection layer and classifier. By semi-superiised, we mean that only few of nodes used for training are labeled. (eemi-)supervieed 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 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 ie.,, 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 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-) >sppevisuee methods, and implement them in the same framework/testhed. Contrastive methods include Deep- [15], Graph2Gauss [6]. SCE [56]. DGI [44], GRACE [62]. GCA [63] and GraphCL [52], which are main competitors. Note that GRACE, GCA and GraphCL are based on multi- and data augmenta- tion, 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 statisties [26, 25, 27]. We compare results with representative jeppe-ssuee GCN [22], GAT' [44] and MixHop [1] models. SGC and S²GC 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-S²GC and RP-S'GC, 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 S'GC, and we name them COLES- GCN, COLES-SCEE and COLES-S'GC. As POLES-GCN is multi-layer non-linear encoder, the optimization of COLES-GCN is non-convex. The optimization of COLES-SCO SGC and COLES-S' GC is convex if L- o' Ex L (-) e s and COLES-GCY (Stiefel) is convex w.r.t. P. We set hyperparameters based on the settings described in their papers.
Walk [35], SampeeamEeNNCE developed as an alternative to SraphSAAGE+Sampleeee
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, classifier is trained by applying the logistic regression in the embedding space. For inductive Icarning, methods based on COLES use 5 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 [5c-4, 1e-3, 5c-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 S²GC and COL.S- 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.
6.1 Transductive Learning
In this section, consider transductive learning where all nodes are available in the training process.
Contrastive Embedding Baselines rs. COLES. Table shows that the performance of COLES- GCN and the linear variant, COLES-S-GC, are better than other unsupervised models. In particular, COLES LES-GGN outperforms SampledCdC on all four datasets, which shows that COLES has an advantage over the SampledNCE framework. In addition, COLES-S' GC typically outperforms the
7

---

Table 1: The statistics of datasets.
Dataset
Task
Nodes
Edges
Features
Classes
Cora
Transductive
2,708
5,429
1,433
7
Citeseer
Transductive
3,327
4.732
3,703
6
Pubmed
Transductive
19,717
44,338
500
3
Cora Full
Transductive
19,793
65,311
8,710
70
Ogbn-arxiv Transductive
169.343
1,166,243
128
40
Reddit
Inductive 232,965
11,606,919
602
41
best contrastive baseline DGI by up to 3.4%. In Cora Full, we notice that SCGC underperforms when training with 5 samples. However, COLES-S-GC is able to significantly boost its performance by 9%. On Citeseer with 5 training samples, COLES-S outperforms SCGC by 6.8%. We also note that COLES-GCN (Stiefel) outperforms COLES-GCN (based the soft-orthogonality constraint) by up to 2.7% but its performance below the performance of COLES-S+GC.
Noteworthy is that for sugmentation-basel methods, COLES-GCN with augmentations denoted as COLES-GCN (+Aug) outperforms COLES-GCN without augmentations. COLES- (+Aug) also outperforms GRACE and GCA, and GraphCL in most experiments. Nonetheless, COLES-S without any augmentations outperformed all augmentation based methods.
Finally, Table 7 shows that COLES-S'S GC outperforms all other methods on the challenging Ogbn- arxiv, while using a very small number of trainable parameters.
Semi-supervised GNNs vs. COLES. Table 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-S GC 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-S' outperforms the best semi- suni-supereieed baselines on all four datasets e.g., by 1.7% on Citeseer. Semi-supervine models are affected by the low number of labeled samples, which consistent with [31], e.g., for GAT and MixHop. The accuracy of COLES-GCN and COLES-S is not affected as significantly due to the contrastive setting.
Unsupervised GNNs vs. COLES. SGC and SCGC are unsupervised LGNs as they are spectral filters which do not use labels (except for the classifier). Table 2 shows that COLES- outperforms RP-S*GC and PCA-S²GC under the same size of projections. In most cases, COLES-S*GC also outperforms the unsupervised GC baseline (high-dimensional representation).
Table Mean classification accuracy (%) and the standard dev. over random splits. Numbers of labeled samples per class are in parentheses. The best accuracy per column is in bold. Models are organized into semi- supervisde contrastive and unsupervised groups OOM means out memory.
Method
Cora
Citeseor
Pubmed
Corn Full
(20)
(20)
(20)
GCN
4..
79.421.6
57.744.7
69.42144
65.4+5.2
77.242.1
8.
61.5+0.5
supervised
GAT
71.2+3.5
1.56
54.945.0
1
65.54466
75.4+2.3
43.9-115
56.9+0.6
MixHop
67.945.7
80.0
54.514.3
67.1
64.4
75.742..7
4..5
61.010.7
DeepWalk
60.324.0
70.5=1.9
38.342.9
45.6=2.0
60.3+56
70.8#2.6
38.9-1.4
51.120.7
SamplaaaE
61.3-1.33
74.3+1166
42.343.4
568-19
60.9+5.7
70.3+22.5
32.7+199
45.2++0.9
65.0.13.5
7.88.1.
48.013..
56.111
64.116.1
7..6.1.99
3..011.4
43.6.10.6
Contrustive
Graph2Gauss
72.742.0
76.211.1
60.713.55
65.721.5
67.61339
74.1:12.1
38.911
49.310.5
SCE
74.3:2.7
80.211.1
65.412.9
7..7.1.2
65.71.6.0
75.8.12.2
50.711.5
60.6.10.6
DGI
72.9:4.00
78.1118
65.743.6
71.11.11
65.315.7
73.912.3
50.5114
58.410.6
COLES-GCN
73.8=3.4
80.8=13
66.0+22.6
69.0=113
62.7+446
72.742.1
47.321.5
58,920.5
COLES- BCN (Stiefel)
75.0=33.4
81.0=133
67.942.3
71.7=0.9
62.6+500
73.24-2.6
47.6-12
59,240.5
COLES-S'CC GC
76.5=2.6
81.5112
67.542.2
71.3=10
66.025.2
77.4:99
508=14
618820.5
GmphhCI.
72.6.14.2
78.3
65.6.3..
71.1008
0OM
0OM
OOM
OOM
Contrastivg
GRACE
64.9+44.2
73.9+116
6188339
68.41.6
0OM
00M
OOM
0OM
Augmentation
GCA
61.5.4.99
7.
43.21.3.6
55.7.1.9
0OM
0OM
OOM
OOM
COLES OCN (+Aug)
75.3:3.3
81.01.3
66.742.3
69.113
63.915.0
73.412.5
48.021.2
59.410.5
SGC
63.94-5.4
78.3+1.9
59.543.4
69.8-4
65.8+4.4
76.342.3
46.0+22
17.74
Unsupervised
S'GC
71.424.4
81.3+1.2
60.344.00
69.5=12
67.6142
73.3+2.0
41.8=1.7
60.0+0.5
PCA-S-GC
72.143.8
81.2+133
61.043.5
68.8+13
67,544.3
73.24-.00
42.3+-177
59.34-..6
RP-S'
65.9-44.6
78.1=112
5144332
61.7-16
66.145.0
72.5+11.9
31.5+114
48.740.6

---

Table 3: The influence of the number (x) of neg- ative Laplacian graphs COLES-S GC. Paren- theses show the no. of labeled samples p/class.
Table 4: The influence of the number (k) neg- ative Laplacian graphs COLES- GCN. Paren- theses show the no. of labeled samples p/class.
5
10
0
5
10
Cora (20)
79.88
81.43
81.18
81.17
Cora
(20)
75.70
80.90
80.87
80.90
Cora
(5)
70.12
76.24
75.89
75.79
Cora
(5)
60.97
74.14
74.11
74.07
Cileseer
(20)
69.42
70.71
70.61
70.61
Citeseer
(20)
60.61
69.04
69.21
69.08
Cileseer
(5)
58.17
67.03
66.96
67.04
Citeseer
(5)
45.31
65.85
66.08
66.01
Table 5: The performance given various choices of the generalized mean Mp for the uniformity loss.
Method
Cor
Citeseer
Pubmed
Cora Full
(20)
(5)
(20)
(20)
(20)
Geometric (Ma) (COLES (GC)
76.51.2.6
81.51122
67.512.2
71.3.1.00
66.0.15.2
77.41..9
50.8 1.4
61.810.5
Arithmetic (M1) (SoftMax-Comtr)
71.8+3.0
77.6+13
63.243.1
69.34088
65.944.3
77.1+1.5
49.2-1.4
60.64-0.6
Harmonic (M-1)
75.2.13.5
80.7112
64.7.22.4
70.9.10.9
65.9.5.5
73.912.4
48.0 1.6
59.7.1.6
Quadratic (M2)
72.3+2.55
77.2+13
65.44222
70.7.+0.8
65.6+4.55
77.3+1.5
60.6+-166
Negative Laplacian Eigenmaps. Below, analyze how in Eq. (5) influences the performance. We set & E {0, 1, 5, 10} on COLES-S" GC and COLES-GOR GCN given Cora and Citeseer with 5 and 20 labeled samples per class. The case of K 0 means negative Laplacian Eigenmaps the solution simplifies to regular Laplacian Eigenmaps parametrized by GCN embeddings. Table shows that without the negative Laplacian Eigenmaps, the performance of COLES-$ drops significantly i... 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 K >>> 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 samples per class. Even when 20 samples per class are used, if O. the performance of COLES-GCN drops by 8.4%.
used, thus
6.2 Uniformity Loss as the Generalized Mean (Mp).
Following the analysis presented Section 4.3, Table 5 demonstrates the impact of the choices the uniformity loss on the performance of COLES. To this end, we select the geometric (Mo), arithmetic (M1), harmonic (M-1) ) and quadratic(MM) means as examples of Mp realizing the uniformity loss. On all the investigated datasets, the geometric mean outperforms other variants.
6.3 Inductive Learning
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 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 emoos on Nvidia GTX 1080 GPU (94.0 Micro-F1 is taken from [44]).
Table 6: Test Micro F1 Score (%) averaged over 10 runs on Reddit. Results of other models are from original papers.
Table 7: Mean classification accuracy (%) and the standard dev. over 10 runs on Ogbn-arxiv. Results of other models are from original papers.
Setting
Model
Test
Method
Test Acc.
#Params
SAGE-mean
95.0
MLP
0..50=1.23
110,120
Supervised
SAGE-LSTM
95.4
Node2Vec
[13]
70.07:1..13
21,818,792
SAGE-GCN
93.0
GraphZoom
[10]
71.18+0.18
8,963,624
C&S
[00] 71.26+0.01
5,160
SAGE-mean
89.7
SAGE-mean
[15] 71.49+0.27
218,664
SAGE-LSTM
90.7
GCN
[22] 71.74+0.29
142,888
SAGE-GCN
90.8
DeeperGCN
[30] 71.92:0.17
491,176
FastGCN
93.7
Contrastive
SIGN
[37] 71.9510.11
3,566,128
DGI
94.0
FrameLet
[59] 71.97:0.12
1,633,183
COLES-GCN
94.0
SºGC
[61]
72.01+0.25
10,120
COLES-SGC
94.8
COLES-S2GC
95.4
COLES-SPGC
72.48
10,120

---

Table 8: The clustering performance Cora, Citeseer and Pubmed.
Cora NMI%
Citeseer NM1%
Pubmed NM1%
Method
Input
Acc%
F1%
Acc%
F1%
Acc%
F1%
k-means
Feature
34.65
16.73
25.42
38.49
17.02
30.47
57.32
29.12
57.35
Spectrul-f
Feature
36.26
15.09
25.64
46.23
21.19
33.70
59.91
32.55
58.61
Spectral-g
Graph
34.19
19.49
30.17
25.91
11.84
29.48
39.74
3.46
51.97
DeepWalk
Graph
46,74
31.75
38,06
36.15
9.66
26.70
61.86
16.71
47.06
GAE
Both
53.25
40.69
41.97
41.26
18.34
29.13
64.08
22.97
49.26
VGAE
Both
53.95
38.45
41.50
44.38
22.71
31.88
65.48
25.09
50.95
ARGE
Both
64.00
44.90
61,90
57.30
35.00
$4.60
59.12
23.17
58.41
ARVGE
Both
62.66
45.28
62.15
54,40
26.10
52.90
58,22
20.62
23.04
GCN
Both
59.05
43.06
59.38
45.97
45.57
61.88
25.48
60.70
SGC
Both
62.87
50.05
58.60
52.77
32.90
63.90
69.09
31.64
68.45
SFGC
Both
68.96
54.22
65.43
69.11
42.87
64.65
68,18
31.82
67.81
COLES-GCN
Both
60.74
45.49
59.33
63.28
37.54
59.17
63,46
25.73
63.42
COLES-GCN (Stiefel)
Both
62,46
47.01
59.38
65.17
38,90
60.85
63.56
25.81
63.58
COLES-SGC
Both
65.62
52.32
56,95
68.24
43.09
63.85
69.47
32.31
68.57
COLFS-SSGC
Both
69.70
55.35
63.06
69.20
44.41
64.70
68.76
33,42
68.12
6.4 Node Clustering
We compare COLES-GCN and COLES-S&GC 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 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 Autoen- coder (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 Fl-score (F1). We run each method 10 times on Cora, CiteSeer and PubMed. We report the clustering results Table 8. We set number of propagation steps to 8 for SGC, S²GC, COLES-SGC and COLES-S GC, following the setting of [57]. We note that outperforms GC in most cases, whereas COLES GCN outperforms contrastive GCN on all datasets.
Scalability. GraphS AGE and DGI require neighbor sampling which result in redundant forward/back- ward propagation steps (long runtime). contrast, COL enjoys a straightforward imple- mentation 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-S the cost of eigen-decomposit
depends on (a few seconds on Reddit). The runtime of COLES- SºGC is also favourable in comparison to multi-view augmentation-baased GraphCL. Specifically, COLES-S&GC took 0.3s, 1.4s, 7.3s and 16.4s on Cora, Citeseer, Pubmed and Cora Full, respectively. GraphCL took 110.19s, 101.0s, 2 Sh and > 8h respectively.
7 Conclusions
We have proposed a new network embedding, COnstrative Laplacian HigenmapS (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 S²GC backbones outperforms many unsupervised, contrastive and sepee-ssuee 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- -ineertir,, which results in the Kantorovich-Rutee Rubinsseen duality; COLES essentially minimizes a surrogate of Wasserstein distance, which offers a reasonable transportation plan, and helps avoid pitfalls the JS divergence. Moreover, COLES takes advantage 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-Contrasto
the uniformity loss.
10

---

Acknowledgments and Disclosure of Funding
We would like thank the reviewers for stimulating questions that helped improve several aspects of our analysis. Hao Zhu is supported by an Australian Government Research Training Program (RTP) Scholarship. Ke Sun and Piotr Koniusz supported by CSIRO's Machine Learning and Artificial Intelligence Future Science Platform (MLAI FSP).
References
[1] Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In International Conference on Machine Learning, pages 21-29, 2019.
[2] Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International Conference on Machine Learning, pages 214-223, 2017.
[3] Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, and Nikunj Saun- shi. A theoretical analysis of contrastive unsupervised representation learning. In International Conference on Machine Learning, pages 5628-5637, 2019.
[4] Philip Bachman, R Devon Hjelm, and William Buchwalter. Learning representations by maximizing mutual information across views. arXiv preprint
2019. [5] Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural computation, (36)):133-1396 2003.
[6] Aleksandar Bojchevski and Stephan Günnemann. Deep gaussian embedding graphs: Unsu-
pervised inductive learning via ranking. arXiv preprini 1771v:1707.03815. 2017.
[7] Hongyun Cai, Vincent W Zheng, and Kevin Chen-Chuan Chang. A comprehensive survey of graph embedding: Problems, techniques, and applications. IEEE Transactions Knowledge and Data Engineering. 30(9):1616-))))
2018.
[8] Miguel A. Parreira The elastic embedding algorithm for dimensionality reduction. In International Conference Machine Learning. page 167174 2010.
[9] Shohreh Deldari, Daniel V Smith, Hao Xue, and Flora D Salim. Time series change point detec- tion with self-super contrastive predictive coding. In Proceedings of the Web Conference, pages 31 3124-3135 2021.
[10] Deng, Z Zhao, Y Wang, Zhang, and Z Feng. Graphzoom: A multi-level spectral ap- proach for accurate and scalable graph embedding. In International Conference on Learning Representations, 2020.
[11] Paul ErdHos and Alfréd Rényi. On random graphs. Publicationes Mathematicae, 6:290-297, 1959.
[12] Rafael C Gonzalez, Richard E Woods, et al. Digital image processing, 2002.
[13] Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In ACM SIGKDD international conference on Knowledge discovery and Data Mining, pages 855-864, 2016.
[14] Michael Gutmann and Aapo Hyvärinen. Noise-contrastive estimation: new estimation principle for unnormalized statistical models. In Proceedings of the thirteenth international con- ference on artificial intelligence and statistics, pages 297-304. JMLR Workshop and Conference Proceedings, 2010.
[15] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, pages 1024-1034, 2017.
[16] Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi-view representation learning on graphs. In International Conference Machine Learning, pages 4116-4126, 2020.
[17] Xiaofei He and Partha Niyogi. Locality preserving projections. Advances in Neural Information Processing Systems, 166661, 2004.
[18] R Devon Hjelm, Alex Fedorov, Samuel Mariii-Marchildon, Karan Grewal, Phil Bachman, Adam Trischler, and Yoshua Bengio. Learning deep representations by mutual information estimation and maximization. arXiv preprint arXiv:1808.06670 2018.
11

---

[19] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprini arXiv:2005.0068) 2020.
[20] Qian Huang, Horace He, Abhay Singh, Ser-Nam Lim, and Austin Benson. Combining label propagation and simple models out- pur-orrfomm graph neural networks. In International Conference on Learning Representations, 2021.
[21] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6908 69800, 2014.
[22] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv: 020000009000....... 2016.
[23] Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank, In International Conference on Learning Representations, 2019.
[24] Piotr Koniusz and Hongguang Zhang. Power normalizations in fine- image, few- shot image and graph classification. In IEEE Transactions on Puttern Analysis and Machine Intelligence, 2020. doi:
-ennri [25] Piotr Koniusz, Fei Yan, Philippe- Henri Gosselin, and Krystian Mikolajczyk. Higher-order Occurrence Pooling on Mid- and Low-level Features: Visual Concept Detection. Technical report, INRIA, September 2013. URL https://haat htttp:://hal.inria... www.iiiiiiarir.. fwwhal-//llloo -09922224.
[26] Piotr Koniusz, Fei Yan, and Krystian Mikolajezyk. Comparison of mid-level feature coding approaches and pooling strategics in visual concept detection. Computer Vision and Image Understanding, 117(5))479 492, 2013. ISSN 1077-3142.
[27] Piotr Koniusz, Fei Yan, Philippe- Henri Gosselin, and Krystian Mikolajezyk. Higher-order occurrence pooling for bags-of-wordd Visual concept detection. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2016.
[28] Omer Levy and Yoav Goldberg. Neural word embedding as implicit matrix factorization. Advances in Neural Information Processing Systems, 27:2177-2185, 2014.
[29] Mario Lezcano Casado. Trivializations for gradient-based optimization on manifolds. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bue, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32, 2019.
[30] Guohao Li, Chenxin Xiong, Ali Thabet, and Bernard Ghanem. Deepergen: All you need to train deeper gens. arXiv preprini urXiv:2006.00739, 2020.
[31] Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In AAAI Conference on Artificial Intelligence, pages 3538-3545, 2018.
[32] Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. Efficient estimation of word representations in vector space. arXiv preprint 1rXiv:1301.3781 2013.
[33] Tomas Mikolov, Ilya Sutskever, Kai Chen, Gregory S Corrado, and Jeffrey Dean. Distributed representations of words and phrases and their compositionality. In Advances in Neural Information Processing Systems, 2013.
[34] S Pan, R Hu, G Long, J Jiang, L Yao, and C Zhang, Adversarially regularized graph autoencoder for graph embedding. In International Joint Conference on Artificial Intelligence, 2018.
[35] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 701-710, 2014.
[36] Ignacio Ramirez, Pablo Sprechmann, and Guillermo Sapiro. Classification and clustering via dictionary learning with structured incoherence and shared features. In IEEE Conference on Computer Vision and Puttern Recognition, pages 3501-3508, 2010. 5539964.
doi: 10.1 10.12000
[37] Emanuele Rossi, Fabrizio Frasca, Ben Chamberlain, Davide Eynard, Michael Bronstein, and Federico Monti. Sign: Scalable inception graph neural networks. arXiv preprint 10X1v12004.11198, 2020.
12

---

[38]
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski. and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arXiv:7811.0586. 2018.
[39]
Christian Simon, Piotr Koniusz, Richard Nock, and Mehrtash Harandi. Adaptive subspaces for few-shot learning. In IEEE Conference on Computer Vision and Puttern Recognition, 2020.
[40] Ke Sun, Piotr Koniusz, and Zhen Wang. Fisher-bures adversary graph convolutional networks. Conference on Uncertainty in Artificial Intelligence, 115:465 4455, 2019.
[41] Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Large- scale information network embedding. In International Conference on World Wide Web, pages 1067-1077, 2015.
[42] Joshua B Tenenbaum, Vin De Silva, and John C Langford. A global geometric framework for nonlinear dimensionality reduction, Science, 29065500):211-22333, 2000.
[43] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 1010. 10903, 2017.
[44] Petar Velickovic, William Fedus, William I. Hamilton, Pietro Lio, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. In International Conference on Learning Representations, 2019.
[45] Cédric Villani. Optimal Transport, Old and New. Springer- Vpringer-Verlag
Verlag Berlin Heidelberg, 2009.
[46] Kuansan Wang. Zhihong Shen, Chiyuan Huang, Chieh-Han Wu, Yuxiao Dong, and Anshul Kanakia. Microsoft academic graph: When experts are not enough. Quantitative Science Studies, 1(1):396-413) 2020.
[47] Tongzhou Wang and Phillip Isola. Understanding contrastive representation learning through alignment and uniformity the hypersphere. In International Conference Machine Learning, volume 119, pages 9929-9939, 2020.
[48] Lilian Weng. From GAN to WGAN, arXiv preprint arXiv:1904.0899) 2019.
[49] Felix Wu, Tianyi Zhang, Amauri Holanda de Souza Jr, Christopher Fifty, Tao Yu, and Kilian Q Weinberger. Simplifying graph convolutional networks. arXiv preprint 2019.
0513,
[50] Zhen Yang. Ming Ding, Chang Zhou, Hongxia Yang. Jingren Zhou, and Jie Tang. Understanding negative sampling in graph representation learning. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1676-1676, 2020.
[51] Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International Conference on Machine Learning, pages 40-48, 2016.
[52] Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang. and Yang Shen. Graph contrastive learning with augmentations. Advances in Neural Information Processing Systems, 33:5812-5823. 2020.
[53] Hanqing Zeng. Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graphsaint: Graph sampling based inductive learning method. arXiv preprint 1rXiv:19070049331 2019.
[54] Hongguang Zhang, Piotr Koniusz, Songlei Jian, Hongdong Li, and Philip H. S. Torr. Rethinking class relations: Absolute-relative supervised and unsupervised few-shot learning. In IEEE Conference on Computer Vision and Pattern Recognition, pages 9432-9441, 2021.
[55] Shan Zhang, Dawei Luo, Lei Wang, and Piotr Koniusz. Few-shot object detection by second- order pooling. In Asian Conference on Computer Vision 2020.
[56) Shengzhong Zhang, Zengfeng Huang, Haicang Zhou, and Ziang Zhou. Sce: Scalable network embedding from sparsest cut. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 257-265, 2020.
[57] Xiaotong Zhang, Han Liu, Qimai Li, and Xiao-Ming Wu. Attributed graph clustering via adaptive graph convolution. arXiv preprint /906v: 10, 2019.
[58] Yifei Zhang, Hao Zhu, Ziqiao Meng, Piotr Koniusz, and Irwin King. Graph-adaptive rectified linear unit for graph neural networks. In Proceedings of the Web Conference, 2022.
[59] Xuebin Zheng, Bingxin Zhou, Junbin Gao, Yuguang Wang, Pietro Lió, Ming Li, and Guido Montufar. How framelets enhance graph neural networks. In Marina Meila and Tong Zhang, editors, International Conference on Machine Learning, volume 139, pages 12761-12777 2021.
13

---

[60] Hao Zhu and Piotr Koniusz. Refine:
Random range finder for network embedding. In ACM Conference on Information and Knowledge Management, 2021.
[61] Hao Zhu and Piotr Koniusz. Simple spectral graph convolution. In International Conference on Learning Representations, 2021.
[62] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep graph contrastive representation learning. arXiv preprint arXiv:2006. 04131, 2020.
[63] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Graph contrastive learning with adaptive augmentation. In Proceedings of the Web Conference, pages 2069-2080, 2021.
14


Reviews:
[{"review_id": "nbRAU35qBHx", "reviewer": "Reviewer_mr5C", "summary": "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. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros: \n      1) This paper is organised well and clearly written.\n      2) The idea to connect the Laplacian Eigenmaps and contrastive learning is novel.\n      3) There are both theoretical analysis and empirical results supporting the proposed method.\n \n\nCons: \n      1) It would be better if the authors can give more details on how the adjacency $\\textbf{ W}$ is generated.\nIf the $\\textbf{ W}$ is generated through k-nearest neighbours how can the computational complexity be handled reasonably with large datasets?\n      2) The examples on when the methods using JS divergence may underperform have been given, but I think the paper would also benefit from providing more insights on when the proposed method would outperform the traditional Laplacian Eignemaps.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I understand this paper focuses more on methodology part, but I suggest the authors should discuss the potential negative societal impact of their work,  probably in terms of applications. It is currentluy missing from the manuscript.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}, {"review_id": "b3nKLZ4PM-a", "reviewer": "Reviewer_Gh8g", "summary": "In this article, the authors extended the classic Laplacian eigenmaps to the form of contrastive learning and proposed a new graph contrastive representation learning model. The authors also gave some theoretical analysis about their proposed contrastive learning loss.", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The authors extended the classic Laplacian eigenmaps to the form of contrastive learning, it seems that the experimental results are good. However, the problem studied in this paper is not new. I think the novelty is incremental. In the current version, I have the following suggestions:\n1.\tEq. (6) should be explained in more detail about F.\n2.\tMissing some important related works about graph contrastive representation learning, e.g., Graph contrastive learning with augmentations (You et al., NeurIPS 2020).\n3.\tWhat are the advantages of the proposed method compared to You et al., NeurIPS 2020.\n4.\tThe experimental results in Table 1 and 7 are not solid enough to verify the effectiveness of the proposed method, since there lack some state-of-the-art methods for comparison. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not sufficient", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "About eight hours."}, "extra_text": {}}, {"review_id": "V5Kgz9zTxMz", "reviewer": "Reviewer_8s4v", "summary": "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. \n\n-- after rebuttal ---\nMost of my concerns are solved, so I change my score from 5 to 6.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n1. The paper is written clearly.\n\n2. The experimental results of different tasks demonstrate the usefulness of the proposed method. The implementation details are provided. \n\n3. Connecting NCE with Laplacian eigenmap provides an interesting paradigm of node embedding, which is promising.\n\nCons:\n1. The introduction of GAN between Line 121 and Line 137 is redundant in my opinion — the conclusion has been given in the paper of WGAN. Compressing this part will give more space and the authors can move more derivations from the supplementary file to the main paper.\n\n2. The Lipschitz continuity of g(u) (and COLES) becomes obvious because the authors have claimed the linearity of the target model. Additionally, it seems unnecessary to derive “||u-u’||_2” in Line 155 and the following inequality. \n\n3. I am not sure about the superiority of “block-contrastive loss”. As the authors claimed in 163, the block-contrastive loss is a lower bound of pairwise-contrastive loss. However, if my understanding is correct, the objective function is minimizing the loss. I don’t think minimizing a lower bound of an objective function. (For example, EM is reasonable because it minimized an upper bound of MLE; a main drawback of WGAN is that it can just minimize a lower bound of Wasserstein distance.)\n\n4. Additionally, different from classic WGAN, the authors consider the Wasserstein distance between conditional generation and the condition corresponds to the model parameters (i.e. v). In other words, learning the embedding u’s conditioned on v will influence the learning of other nodes’ embeddings that conditioned on the u’s. Such a non-i.i.d. situation makes the feasible domain of g_v(u) in Eq. (11) changes during training. Maybe the authors should emphasize and analyze this difference.\n\n5. The parameters of COLES are constrained (as shown in Eq. (6)). How to achieve the constraints in the framework of SGD is not explained clearly. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I did not find any obvious or potential negative societal impact of this work.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "K1CuXTHZQLM", "reviewer": "Reviewer_CRCP", "summary": "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. \n\nThe 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. \n\nBy 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. \n\nThe 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. \n\nThe 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.  ", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: \nThe approach seems simple, straightforward but original. They use the log-linear contrast function, instead of the sigmoid, which allows reformulation as a generalised eigenvalue problem. If the contrastive learning problem is interpreted as a GAN, then convergence is in the Wasserstein topology which does not suffering from the vanishing gradient problem when the two measures do not have overlapping support. \n\nQuality: The submission is technically sound, with extensive empirical evaluation and sufficient theoretical justification.  However, the authors do not sufficiently discuss the weakness of their approach. For example, the reason for the choice of log linear loss, or its interpretation. Is then Laplacian eigen map just one example of contrastive learning or are there some optimality results in this direction?\n\nClarity: The paper starts off clearly written but in some sections, feels disjointed. For example section 4.1 lines 128-152 could have been summarised succinctly as most of the derivation there is well known. The empirical evaluation is described adequately. \n\nSignificance: \nThe paper presents a thoughtful approach to contrastive graph embedding as generalised eigen value problem. If explored further, the results may provide better understanding of contrastive graph embedding  approach. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": " Not applicable.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper had very split reviews and required some thought when coming to a recommendation. The authors provided very thorough responses to each reviewer's critiques. While the two positive reviews responded saying they were satisfied with the author responses, neither of the negative reviewers responded to the author feedback. One negative reviewer's only objection was a lack of comparison against You et al. 2020. The author's provided such a comparison in the response, showing good results for their method relative to the baseline. The other reviewer had more detailed critiques, but from my estimation of the author's response, those critiques were well rebutted. Unfortunately I do not know if the reviewer themself thought the critiques were answered well. I am inclined to recommend acceptance for this paper, on the basis of the very thorough responses which I believe answered most of the reviewer critiques, and the failure of the reviewers themselves to answer the authors.
Decision: Accept (Poster)