Generalized Laplacian Eigenmaps
Authors: Hao Zhu
Piotr Koniusz
Venue: NeurIPS 2022 Accept (2022)
Keywords: GCL
graph contrastive learning
node embedding
logdet
rank minimization

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. COLES, a recent graph contrastive method combines traditional graph embedding and negative sampling into one framework. COLES in fact minimizes the trace difference between the within-class scatter matrix encapsulating the graph connectivity and the total scatter matrix encapsulating negative sampling. In this paper, we propose a more essential framework for graph embedding, called Generalized Laplacian EigeNmaps (GLEN), which learns a graph representation by maximizing the rank difference between the  total scatter matrix and the within-class scatter matrix, resulting in the minimum class separation guarantee. However, the rank difference minimization is an NP-hard problem. Thus, we replace the trace difference that corresponds to the difference of nuclear norms by the difference of LogDet expressions, which we argue is a more accurate surrogate for the NP-hard rank difference than the trace difference.  While enjoying a lesser computational cost, the difference of LogDet terms is lower-bounded by the Affine-invariant Riemannian metric (AIRM) and  Jesen-Bregman the LogDet Divergence (JBLD), and upper-bounded by AIRM scaled by the factor of $\sqrt{m}$. We show that GLEN offers favourable accuracy/scalability compared to  state-of-the-art baselines.

Generalized Laplacian Eigenmaps
Hao Zhu
Piotr Koniusz *&
DCt161/CSSRO Australlian National University catnnhaazzhu@ggail... piotr. miorr.onniuszddaaal.lccom cesioo.u
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 preserve intrinsic and structural properties of a graph. COLES, recent graph contrastive method combines traditional graph embedding and negative sampling into one framework. COLES in fact minimizes the trace difference between the within-class scatter matrix encapsulating the graph connectivity and the total scatter matrix encapsulating negative sampling. In this paper, we propose more essential framework for graph embedding, called Gen- eralized Laplacian EigeNmaps (GLEN), which learns graph representation by maximizing the rank difference between the total scatter matrix and the within-class scatter matrix, resulting in the minimum class separation guarantee. However, the rank difference minimization is NP-hard problem. Thus, we replace the trace difference that corresponds to the difference nuclear norms by the difference LogDet expressions, which argue is rank difference than the trace difference. While enjoying a lesser computational cost, the difference of LogDet terms is bower-bounded by the iffirneinvariant Riemannian metric (AIRM) and upper-bounded by AIRM scaled by the factor mm. We show on popular benchmarks/backbonke that GLEN offers favourable accuracy/scalability compared to state-of-the-ee baselines.
accurate surrogate for the NP-hard
Introduction
Laplacian Eigenmaps [3] and IsoMap [36] graph embedding methods that reduce the dimension- ality of data by assuming the data exists on a low-dimensional manifold. The objective function in such models encourages node embeddings lie near each other in the embedding space if nodes close to each other in the original space. While the classical methods capture the related node pairs, they neglect modeling unrelated node pairs.
In contrast, modern graph embedding models such as [35, 10, 44] and Graph Contrastive Learning (GCL) [37, 56, 11, 57, 55] are unified under the (Sampled) Noise Contrastive Estimation framework. called (Sampled)NCE) [27, 23]. Most of GCL methods do not incorporate the graph information into the loss but follow the setting from computer vision, i.e., they assume that randomly drawn pairs should be dissimilar, whereas the original sample and its augmentations should be similar [39]. In contrast, COntrastive Laplacian EigenmapS (COLES) [55] is framework which combines (graph) neural network with Laplacian eigenmaps utilizing the graph Laplacian matrix within a contrastive loss. Based the NCE framework, COLES minimizes the trace difference of Laplacians.
In this paper, we analyze the relation among within-class, between-class and total seatter matrices under the rank inequality, and prove that, under simple assumption, the distance between any dissimilar (negative) samples would be greater/equal than the inter-class distance between their corresponding class centers. Based on such condition, we derive GLEN, reformulation of graph embedding into a rank difference problem, which a more general framework than other graph
'The corresponding author.
Code: https://github http//allehhzzhh///aaa GLEN.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

embedding frameworks, i..., under specific relaxations of the rank difference problem, we can recover different frameworks. To that end, we demonstrate how to optimize the rank difference problem with a difference of LogDet expressions, differentiable relaxation suitable for use with (graph) neural networks. We consider other surrogates of the rank difference problem, based on the Nuclear norm, "y-uclear norm, Schatten norm, and the Geman norm. Moreover, we provide theoretical considerations regarding the low-rank optimization and connection to the Riemannian manifold in order to interpret our approach.
In summary, our contributions are threefold:
We propose rank-based condition connecting within-class, between-class and total scatter matrices under which we provide the minimum class separation guarantee. We propose a loss function, Generalized Laplacian EigenNaps (GLEN), that realizes this condition.
ii As the rank difference problem is NP-hard, we consider a difference of LogDet surrogate to learn node embeddings, as opposed to the trace difference (an upper bound of the difference of LogDet terms) used by other graph embedding models. We also consider other surrogates.
iii. We study the distance between symmetric positive (eeni-)defintte matrices and the LogDet- based relaxation of GLEN. While enjoying fewer computations, the difference of LogDet terms of GLEN enjoys the scaled by /mn as an upper bound. We explain how GLEN connects to other graph embeddings.
Riemannian metrie (AIRM) for a lower bound and AIRM
2 Related Works
Graph Embeddings. By assuming that the data lies on low-dimensional manifold, graph em- bedding methods such as Laplacian Eigenmaps [3] and IsoMap [36] optimize low-dimensional data embeddings. These methods [5] construct similarity graph by measuring the similarity of high-dimensional feature vectors and embed the nodes into a low-dimeniional space.
WalpWalk [31] uses truncated random walks to explore the graph structure. and the skip- -ram model for word embedding determine the embedding vectors of nodes. By setting the walk length to one and using negative sampling [26], LINE [35] explores a similar idea with an explicit objective function while REFINE [52] imposes additional orthogonality constraints which deem REFINE extremely fast. Vec [9] interpolates between breadth- and depth-first sampling. COLES [55] unifies traditional graph embedding and negative sampling by introducing a positive contrastive term that captures the graph structure, and negative contrastive random sampling. COLES solves the trace difference problem akin to traditional graph embedding models [43]. In this paper, we propose more general loss for graph embedding, i.e., COLES solves the trace difference (Nuclear norms difference) relaxation of GLEN.
Graph embedding techniques [43] provide general framework for dimensionality reduction such as Principal Component Analysis (PCA), Linear Discriminant Analysis (L.DA), and Locality Pre- serving Projections (LPP) [12]. All methods within this category can be considered as solving the same problem under varying assumptions, iee,, maximising the intra- and inter-class separation by optimizing the trace difference, also used in metric learning [22]. However, such a family of objective functions is not motivated by the guarantee on the minimum class separation between feature vectors from different categories. GLEN, in its purest Na-hard form, provides the minimum class separation guarantee and can be realised by several formulations depending on chosen trade-offs.
Unsupervised Representation Learning for Graph Neural Networks (GNN). Unsupervised GNN training can be reconstruction- contrastive- diffusion-based. To train graph encoder in an unsupervised manner, GCN [17] minimizes a reconstruction error which only considers the similarity matrix and ignores the dissimilarity information. At various scales of the graph, contrastive methods determine the positive and negative sets, For example, local-local CL and global-local CL strategies are highly popular. GraphS [10], inspired by DeepWall [31], uses the contrastive loss which encourages neighbor nodes to have similar representations, while preserving dissimilarity between representations of disparate nodes. DGI [37], inspired by Deep InfoMax (DIM) [13], uses an objective with global-local sampling strategy to maximize the Mutual Information (MI) between
global and local graph embeddings. Augmented Multiscale Deep InfoMax (AMDIM) [2] maximizes MI between multiple data views. MVRLG [11] contrasts encodings from first-order neighbors and a graph diffusion. Fisher-Bures Adversary GCN [34] treats the graph as generated w.r.t. some observation noise. COSTA [50] constructs the views by injecting features with the random noisc.

---

(a) Rank(S)) 0
(b) Rank(St) =
(c) Rank(s)) =
Figure 1: Three cases under our Condition 1, i.e. Rank(S.) Rank (S..) Rank(S,). The red line and plane indicate the space of class centers. The black dots represent class centers. Other colored lines or ellipses represent the spaces of different categories. We show a non-exhaustive set of cases.
However, such contrastive approaches often require thousands of epochs to converge and perform well. In addition, many contrastive losses have an exponential increase in memory overhead w.r.t. the number of nodes. In contrast, our method does not explicitly use the local-local setting but the total scatter matrix, and thus saves computational and storage cost.
Linear GNNs, i.e., SGC [42] and S2GC [53], capture the neighborhood and increasingly larger neighborhoods of each node due to the diffusion, respectively. SGC and S*GC have no projection layer, thus the size of embeddings is equal to the input dimension. GLEN can learn a projection layer an unsupervised manner with linear function or Multi- Layer Perceptron (MLP) applied to linear GNNs or any other GNN models [18, 34, 491, etc.
3 Preliminaries
Let G E) be simple, connected and undirected graph with n= nodes and m = [ edges. Let i E f1.... ... .n) be the node index of G, and dj be the degree of node j of G. Let W be the adjacency matrix, and be the diagonal matrix containing degrees of nodes. Let
Notations.
X E Baxd denote the node feature matrix where each node is associated with feature vector Let the normalized graph Laplacian matrix be defined as
X, E R
W E $ a symmetric positive semi-definite matrix and W = D D-11/ 1/2 ST(+)) is set of symmetric positive (semi- ddefinite matrices. Let Z fe XX) E Raxm be a generalized node embedding, i.e., X could be identity matrix (e.g., no node attributes), (X) could be GNN or a linear function with parameters O. Scalans/vectors/matiiee are denoted by lowercase regular/lowercas bold/uppercase bold fonts.
3.1 Scatter Matrices
Below are given standard definitions of seatter matrices, including the total scatter matrix S, Sm the within-class matrix S., E 3t +(+) and between- -lass matrix S, S +++))
+(+)*
S, =
[z 2) (z. 2) = =z" (I- W.)z
where
W, = eee
1=1
S
(zi My )z, -my T (I W Ww where
W w
eT
The
1=1
c=1
S = Σ ne (me- (
( Z)T
(1)
Let be n-dimensional vector with all coefficients equal one, I be an identity matrix, S, be the total scatter (covariance) matrix, and The be the mean all samples. Let Hy, E R be the class center of the i-th sample and Mcc E Rm be the c-th class center. Let the total number of categories be given by C, whereas n. be the number of samples for the e-th category. Let e 1 be a vector where given coefficient indexed by node is equal one if its node is of class otherwise it is equal zero. We note that both S, and S... can take form akin to Laplacian eigenmaps such that W, and W., w are the corresponding normalized adjacent matrices. Let also define graph Laplacian matrices
3

---

= W. E S and L. =I- W. E which will be used in the sequel. Importantly, let us assume that graph Laplacian matrix L containing graph links could be seen as a noisy version of L in which all nodes of a given class connect under the weight equal 1/me-
Observe that S, _ + Sa. Thus, Rank(S,) (an + Rank(Sa) due the rank inequality. Below we highlight the condition underpinning the subsequent motivation:
Condition 1. Rank(S,) = Rank(S..)) + Rank(S.).
3.2 Motivation
Figure 1 shows some three optimal solutions for Condition 1. The rank of between-class scatter matrix S, for the whole dataset is most C (where C' is the number of classes). Since
Rank(AB) I min(Rank (A), Rank(B)), we have (ank(S-1S,) < Rank(S,) I C - 1. The
rank the number of non-zero eigenvalues of a matrix so S has at most C - 1 non-zero
eigenvalues. Condition implies that Rank(S- guarantee under that condition.
0 results in the minimum class separation
Theorem Let the feature dimension be larger than the class number (i.e., m > C) and Condition I hold. Then, the minimum class separation is equal to the distance between class centers. In other words, the distance between any two vectors 2; and 2 with labels ys # yj greaterlequal the distance between class centers pay, and pyy
M My ll2 S I|z z, 22 Vy F My
i.j E {1...., ,C}.
(2)
Proof. As Sw is the orthogonal complement of So, i.e., S = S. S, UEUT, S.
U1:4 U I.k: and S2 = U Ix+mmmm U k E is the representation under the basis U and 1(k+
where S k < m. Let z; = My. + +U e, where
because only top k components 1:k
represent S... Thus, the orthogonal projection U fulfills ||U++1m (z. 2 I Iz Zj 2- Moreover,
(z. ( Uk+ I:m (U ex) = 0. That is, all {ze: y/ c} are projected onto the mean Me. Thus, the inequality in Eq. 2 holds.
Theorem guarantees the worst inter-class distance Figure shows some cases that meet Condi- tion 1. Figure la shows the case for which the class centers collapse to a single point and thus the inter-class distance equals zero (collapse of the feature space). Figures 1b and Ic show other cases.
Methodology
Condition points promising research direction in learning discriminative feature spaces. However, optimizing over the rank is NP-hard and non-difierentiable. In what follows, we provide the formulation of Generalized Laplacian EigeNmaps (GLEN) and its relaxation, which is differentiable.
4.1 Generalized Laplacian Eigenmaps
As solving Condition is NP-hard, we propose a relaxation where Rank(S,) is encouraged to be as large as possible (bounded by the feature dimension m). On the contrary, if Rank(S,) Rank(S,) then the small RS.)(S...) limits the feature diversity. In the extreme case, if (S.k(S..)) = 0, the feature representation collapses. Larger 0 < Rank(Ss) C - improves the inter-class diversity.
We propose a new Generalized Laplacian EigeNmaps (GLEN) framework for unsupervised network embedding. In the most general form, GLEN maximizes the difference of rank terms:
O arg max Rank (S, (fe( - Rank (S (X)))
(3)
As the general matrix Rank Minimization Problem (RMP) [7] is NP-hard and so is the difference of rank terms in Eq. 3, we relax this problem by the difference of LogDet terms that serve as a surrogate of the Na-hard problem. Appendix I derives GLEN from the SampledNCE framework.
We write S but St rank-deficient, -1 is replaced with the Moore-Penrose inverse (pscudo-inversc). 'Other graph embedding models that maximize/minimize inter-/intra-cle distances have such guarantees.

---

GLEN (LogDet relaxation).
Define:
8( Swi A) log det aS;) Alog det aSw),
(4)
where À 2 0 controls the impact of log det If À = 0, 6(-) encourages Rank(fe(X)) = m.
II. Let S = Le,X) and S = fe(X) (X)).. Then the LogDet relaxation
becomes:
log det (I+ aaaee TT.eeeeeii//lllll L. (5) @* arg max log det ( LxJe(X)) Lx.eee))
where ensures + (
as fx(X) (X) may be S leading to det(fa (X) (X)) = O. Thus, we use log det(I + aS) as a smooth surrogate for Rank(S).
Proposition 1. Let (S) be the vector of eigenvalues of matrix E Shit and Eig(S) be diagonal matrix with (S) as its diagonal. Let S,S' E St(+) and a > 0. Then, 5(S, a a, A) = 6(Eig(S) (S), Eig(S'); a, A). i.e, 8(.) depends on eigenvalues rather than eigenvectors of S and S'.
Proof. The proof follows from the equality de + a.S) = II. oz aS) II, + 0o (S)) det(I + a ESg( Thus ö(S, S'; a, A) log det aS) ) - x log det(1 + aS') = log det
Eig () Alog de + Eig(S") = (SEig(S) a,,
5 Theoretical Analysis
Below, we compare our approach and other methods by looking at the low-rank optimization and (ii) the non- oon-uuclidean distances between symmetric positive (semi-)definie matrices.
5.1 Nuclear Norm vs. LogDet for Rank Minimization
Claim 1. COLES [55] is convex relaxation (using the nuclear norm) of the rank difference in Eq. 3:
θ arrg arg Tr (X)
-AAT (
- -
s.t. ((fe(X)) B, (6)
where Tr (X) fX)) |S and Tr
(X) |S
The nuclear norm ||e can regarded as the l norm over singular values. As the & norm induces sparsity, the nuclear norm encourages sparse singular values leading to low-rank solutions. A If fe (X) fX( is restricted to be diagonal, Iife (X) fe [X]] = DDag (X) (X( | and the nuclear norm surrogate for the rank minimization reduces the l norm surrogate for the cardinality (rank) minimization. However, for the m-dimensional embedding, the solution of trace difference lies subspace of dimension less than prevents the dimensional collapse, i.e., fe( (X) = I.
[3]. Thus, the constraint (X)e(()) B
Compared with the rrace-based relaxation, LogDet is more suitable for cardinality minimization as it is less sensitive to large singular values. Also, the difference of LogDet terms does not require decorrelation features to prevent the dimensional collapse. We discuss this matter in Appendix A. In our case, the difference of LogDet terms is always bounded by the difference of trace terms as follows.
Proposition 2. Given an embedding matrix fe(X)= E Raxmm a a.fixed small constant >> 0, we have the following inequality:
log det (I + aS;) log det (I + aSw) a Tr(S - -Sw).
Proof.
log det (I+aS;) - det (I aS.) = det
det (I+a Eig S:)) - log det (I a Eig(Sw))
(8)
=Tr (log(I + Eig(S,) log(1 + Eig(S.)) Tr(S. Sw).
Proposition 2 is also related to the inequality Rank(S) < log det SS) Tr(S) [7].
5

---

5.2 Distance between Symmetric Positive (Semi-)Definite Matrices.
Below, we provide perspective on non-Euclidean distances between matrices from S compare the proposed method with other graph embeddings, e.g., Laplacian Eigenmaps [3] and COLES [55]. For clarity, we also reformulate the Laplacian eigenmaps and COLES into forms in Prop. 3 and
Proposition Laplacian Eigenmaps [3] method equals to maximizing the Frobenius norm:
- = arg max (X) -L
s.A.
fe(X) =I
Proposition 4. Contrastive Laplacian Eigenmaps [55] equals to maximizing the difference of Frobenius norm terms:
arg max -1- - s.t. (e(X) = (10)
Proof.
[X)((X) -
LL') +L
(11)
constant 2Tr(fe(X)L/e(x)) 20.
Note that Eq. 9 encourages the linear kernel matrix fe (X) to be close to W. while Eq. 10 encourage the linear kernel matrix to be far from the W... at the same time.
Our loss follows the -uclideld geometry. Below, we demonstrate the relation of Eq. 4 the Affine-invariant Riemannian metric (AIRM). Indeed, our loss function is bounded from both sides by AIRM and AIRM scaled by /m respectively.
Proposition 5. Let (S)) be the vector of eigenvalues S. for any matrix St, S..
Sm
we have:
|oog (I
Sw) -
I log det [I S,) log det Sw))
v m
log (1 + S.2 S..) (I -.)--1)) -/2)
(12)
Proof. Given A = I+ S₁ and B = I- Sw, we have:
log det(A) log det (B) log(det(A) de 1) log(de((A)det((3 det(BB (B-
(13)
= Tr (B 1/2 (P-ABB1))
We have Tr(A) = [I)()) |A]| = (A)(ll and ||x||2 S |x||1 S /ml|xx|2-
Thus, Eq. 4 is trying to find mapping function maximizing an approximation of AIRM distance between the total scatter matrix and the within-class matrix.
5.3 Relationship of the LogDet model to the Schatten norm
Below we demonstrate the relationship between the LogDet, Trace and Rank operators, respectively, under the Schatten norm [28] framework. Essential is the following family of objective functions:
1 Σ log (Oo, 7) log det (oS +DI), a,7 O,
fa,
(14)
where (S),) 1...., m, are the eigenvalues of either S, E S or S., E mm which are the total scatter matrix and the within scatter matrix from our experiments, respectively. Moreover, we define a normalization constant where or e log(a + 7) as detailed below.
Given 1, we have:
Sp (S)
m
(o.(S)+ 7))) 1/8
lim p-00
(S) where Sy =
Σ
(15)

---

From the asymptotic analysis, we conclude that the LogDet is an arbitrarily accurate rational ap- proximation of to (the so-called pseudo-nome counting non-zero elements) over the eigenvalues of S.
The case p yields the nuclear norm (trace) which makes the 'smoothed" rank difference of GLEN become equivalent of COLES. The opposing limit case, denoted as recovers the LogDet formula.
One can also recover the exact Rank from the LogDet formulation by:
lim f Rank(S) if logg1 + a). a
(16)
This is apparent because:
lim log(1 + a0;)) log(1 + aa)
log(1 + (0;;) log(1 + a)
=1 if oe 0 and
lim
if o 0.
(17)
Experiments
We evaluate GLEN (its relaxation) transductive and inductive node classification tasks and node clustering, GLEN is compared to popular unsupervised, contrastive, and (semi-)supervised approaches. Except for the classifier, unsupervised models do similarity, contrastive models employ the contrastive setting. Labels are used to train the projection layer and classifier in semi-supervised models. A fraction of nodes (i.e., 20 per class) used for training are labeled for semi-supervised setting. A SoftMax classifier is used for juuperisupervieed models, while logistic regression classifier is used for unsupervised and contrastive approaches. See Appendix E for implementation details.
labels. To learn similarity/dis-
Datasets. GLEN is evaluated on four citation networks: Cora, Citeseer, Pubmed, Cora Full [17, 4] for transductive setting. We also employ the large scale Ogbn-arxiv from OGB [14]. See Appendix D for details of datasets.
Metries. As fixed data splits [45] often on transductive models benefit models that overfit, we average results over 50 random splits for each dataset. We evaluate performance for and 20 samples per class. Nonetheless, we also evaluate our model on the standard splits.
Baseline models. We group baseline models into unsupervised, contrastive and methods, and implement them in the same framework/testhed. Contrastive methods include Deep- Walk [31], GCN+SampledNCE developed as an alternative to AGE+SSleeNN [10].
Table 1: Mean classification accuracy (%) and the standard dev. over 50 random splits. Numbers of labeled samples per class in parentheses. The best accuracy per column is in bold. Models organized into semi-supervised, contrastive and unsupervised groups OOM means out of memory.
Methed
Cora
Citeseer
Pubmed
Cora Full
(20)
(5)
(20)
GCN
67.5+4.88
19.4+1166
57.7+4.77
69.4114
65.4+5.2
77.242.1
49.3+118
61.5+0.55
Semj- supervised
54.915.0
56.9
MixHlop
67.915.7
80.011.4
54.514.3
67.122.0
64.415.6
75.7122.7
47,5115
61.0.0.7
DeepWalk
60.3+4..0
70.5+1.9
38.342.9
45.6+2.0
51.1+0.7
SCN-SanpEeNNCE
61.3=4.3
74.3+1.6
42,3+3.4
$6.8-199
60.9-5.7
70.3+22.5
32.7=199
45.2+0.9
SAGF-SSupIeeNCC
65.0+33.5
73.8+1.5
48.0433.5
43.6+0.6
Graph2Gauss
72.7.12.0
76.2.1.1
60.7.13.5
65.7.1..5
6..6
74.1
38.911.3
49.3
SCE
60.6:10.6
Contrastive
DGI
72.9=2..0
78.1
63.74:3.6
71111.1
65.345.77
73.9422.3
10.3=14
$8.420.6
COLES-GCN
73.8=3.4
80.8+113
66.042.6
69.0==1.
62,74466
72.7--2.1
47.3+1.
58,9+0.5
COLES. GCN (Stiefel)
75.0+33.4
81.0+1.3
67.942.3
71.7-0.9
6..61.500
73.2422.6
47.6112
59.240.5
COLES--POC
77.41199
61.810.5
GLEN-GCN
77.5=2.6
82.721.2
67.6:22.6
72.0=00.9
68.745.7
78.2422
$2.7115
62.020.3
GLEN-SPOC
78.2::2.4
69.112.1
GraphC1.
72.6+44.2
78.3+1177
65.6++3.0
711+008
COM
00M
COM
COM
Coptrastive
GRACE
64.914.2
7.99
Maltiview
GCA
61.324.99
75.811.9
43.24:..6
53.7219
0OM
0OM
COM
0OM
SGC
63.925.4
78.3=19
59.543.4
69.8114
65.814.4
76,342.3
46.0=22
57.741.2
Unsupervised
S-GC
71.444
81.3112
60.314.0
69.5112
67.614.2
73.312.0
41.11.7
60.0.0.5
PCA-S'GC
72.1=3.8
81.2+13
61.043.5
68.811.3
67.5+4.3
73.24:..0
42.3=1.7
59.320.6
RP-S/CC
65.9114.6
78.111.2
51A13.2
61.7116
48.710.6

---

Graph2Gauss [4], SCE [47], DGI [37], GRACE [56], GCA [57], GraphCL [46] and COLES [55],
which are our main competitors. Note that GRACE. GCA and GraphCL are based on multi-view and data augmentation, and GraphCI. is mainly intended for graph classification. We do not study graph
classification requires advanced node pooling with mixed- or high-order statistics [40, 19, 20]. We compare results with representative (semi))supervins models. SGC and SC are unsupervised spectral filter networks. They do not have any learnable parameters. COLES and GLEN could be regarded as dimension reduction techniques for SGC and S'GC, thus we compare them to PCA-S-GC and RP-S²GC, which use PCA and random projections to obtain the projection layer. We set hyperparameters based on the settings described in prior papers.
GCN [17], GAT [37] and MixHop [1]
6.1 Transductive Learning
In this section, we consider transductive learning where all nodes are available in the training process.
COLES vs. GLEN. Table shows the performance of GLEN vs. COLES on two different backbones, i.e. GCN and SCGC. On both backbones. GLEN shows non-trivial improvements on all four datasets. GLEN-S*GC outperforms the COLES by up to 4.6%. Table 2 evaluates GLEN on Cora, Citeseer, PubMed on the standard splits instead of the random splits. See Appendix G for comparisons to additional contrastive learning frameworks.
Contrastive Embedding Baselines GLEN. Table 1 shows that GLEN-GCN and GLEN-S'GC outperform unsupervised models. In particular, GLEN-GCN outperforms GaNplanlE on all four datasets, which shows that GLEN has advantage over the SampledNCE, framework. In addition, GLEN-S outperforms the best contrastive baseline DGI by up to 3.4%. On Cora with training samples, GLEN-S outperforms GC by 6.8%. Finally, Table 3 shows that GC (small number of trainable parameters) outperforms other methods on the challenging Ogbn-arxiv.
Semi-supervised GNNs vs. GLEN. Table 1 shows that the contrastive GCN baselines perform worse than supervupee variants, especially when 20 labeled samples per class are available. In contrast, GLEN-GCN outperformed the supervise GCN on Cora by 10% and 3.4% given 5 and 20 labeled samples per class. GLEN-GCN also outperforms GCN on Citeseer and Pubmed by 9.9% and 5.2% given 5 labeled samples per class. These results show the superiority of GLEN four datasets when the number of samples per class 5. Even for 20 labeled samples per class, GLEN-S outperforms the best remi-supervised baselines on all four datasets egg., by 3.3% on Cora. Semi-supervised models (e.g., GAT and MixHop) are affected by the low number of labeled samples, which is consistent with [25]. The accuracy of GLEN-GCN and GLEN-S*GC is unaffected.
Unsupervised GNNs vs. GLEN. SGC and SCGC are unsupervised linear networks based on spectral filters which do not use labels (except for the classifier). As dimension reduction method, GLEN helps both methods reduce the dimension and achieve discriminative features. Table 1 shows that GLEN-S outperforms GC and PCA-S'GC under the same projection size. GLEN-S²GC also outperforms the unsupervised SCGC bascline (high-dimensional representation).
Table 2: Comparison with other methods on Cora, Citeseer and PubMed on standard splits.
Table 3: Mean classification accuracy (%) and the standard dev. over 10 runs on Ogbn-arxing Results of other models are from original papers.
Cora
Citeseer
Pubmed
Method
Test Acc.
#Params
GCN
81.5
70.3
79.0
GAT
83.0
72.5
79.0
MLP
55.50
110.120
Node2Vec
[9] 70.07=0.13
21.818,792
DaepWalk+F
77.36
64.30
69.65
GraphZoom
[6] 71.1810.188
8,963,624
Node2vec+F
75.44
63.22
70.60
C&S
[15] 71.26+0001
5,160
GAE
73.68
58.21
76.16
SAGE-mean
[10] 71.49+0.27
218,664
VGAE
77.44
59.53
78.00
GCN
[17] 71.74+00.29
142,888
DGI
81.26
69.50
77.70
DeeperGCN
[24] 71.92:10.17
491,176
GRACE
81.9
71.2
80.6
SIGN
[33] 71.9510.11
3,566,128 128
GraphCL
81.89
68.40
OOM
FrameLet
[51] 71.97.10.12
1,633,183
GMI
80.28
65.99
OOM
S.GC
[53] 72.01:10.25
110,120
COLES-GNN
81.9
70.3
79.1
COLES-SPGC
[55] 72.48+0.22
10,
GLEN-S²GC
85.10
71.90
80.72
GLEN-S&GC
72.67+0..6
100
8

---

Table 4: The clustering performance Cora, Citeseer and Pubmed.
Cora NM1%
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
Spectral-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
WeepWalk
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
54.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
$2.77
32.90
63.90
69.09
31.64
68.45
S'GC
Both
68.96
54.22
65,43
69.11
42.87
64.65
68.18
31.82
67.81
COLES-GON
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
39.38
65.17
38.90
60.85
63.56
25.81
63.58
COLES-S'GC
Both
69.70
55.35
63.06
69.20
44.41
64.70
68.76
33.42
68.12
GLEN-GCN
Both
69.27
55.34
62.14
68,25
42.98
64.10
64.64
30.08
64.12
GLEN-S'GC
Both
71.01
56.69
69.01
69.89
45.37
65.70
69.62
34.97
69.33
Table 5: Mean classification accuracy (%) and the standard dev. over 50 random splits. Numbers of labeled samples per class are parentheses. The best accuracy per column is in bold. Models are organized into semi-supervised, contrastive and unsupervised groups. OOM means out memory.
Cora
Citeseer
Pubmed
Cora Full
Method
(20)
(20)
(5)
(20)
(5)
(20)
GLEN (Nucleur Norm)
76.5++2.66
81.5
67.5+22.2
71.3++1.0
66.0+5.2
1..4=1.9
50.8+1.4
61.8+005
GLEN (ry-ncleea norm)
71.8+3.0
77.6
63.243.1
69.3.10.8
71.2444.3
1..
49.21114
60.6:10.6
GI,EN (S, norm)
75.2+33.5
80.7+1.2
64.7+22.4
70.9.+0.9
65.9+5.5
73.9+244
48.0++1.6
59.7+1.6
GLEN (Geman norm)
72.3442.5
77.2=1.3
65.4:12.2
70.7.40..
72.644455
78.3=1.5
49.24:1.5
60.6-:1.6
GLEN (LogDet)
78.2+2.44
83.0=100
69.1#2.1
72.3+009
70.6:3.9
80.1=1.9
53.0+:1.5
62.6#0.55
6.2 Node Clustering
We compare GLEN-GCN and GLEN-S²GC with three types of clustering methods: Methods that use only node features e.g., k-means and spectral clustering (spectral-f) construct similarity matrix with the node features by 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 DeepWall [31].
iii. Attributed graph clustering methods that use node features and the graph: Graph Autoencoder
(GAE), Graph Variational Autoencoder (VGAE) [17], Adversarially Regularized Graph Autoen- coder (ARGE), Var. Graph Autoencoder (ARVGE) [30], SGC [42]. S'GC [53], COLES [55].
We measure and report the clustering Accuracy (Acc), Normalized Mutual Information (NMI) and macro Fl-score (FI). We run each method 10 times on Cora, CiteSeer and PubMed. We set the number of propagation steps to for SGC, SºGC, COLES-S GC and COLES-S* GC following [48]. Table 4 shows that GLEN-S&GC outperforms other methods in all cases, whereas GLEN-GCN outperforms COLES-GCN COLES- (Stiefel) and contrastive GCN on all datasets.
6.3
Comparison of Surrogates of Rank
Table 5 above shows results four additional surrogates of Rank(S):
Nuclear norm: RSx(S) = Σ; (S).
-uclear norm [16]: Ry-NN = E,
(1+))a,(S) (+0((S)
Sp norm [28]: Rs,- = (S)P.
Geman norm [8]: RGemmn = E; a.(S)
7t);(8)

---

6.4 Transductive One-shot Learning on Image Classification Datasets
The most common setting in FSL is the inductive setting. In such a scenario, only samples in the support set can be used to fine-tune the model or learn a function for the inference of query labels. In contrast, in the transductive scenario, the model has access to all the query data (unlabeled) that needs to be classified.
EASE [54] is transductive few-shot learner for so-called episodic image classification. Given feature matrix Z E |Rxm from a CNN backbone (ResNet-12), EASE minimizes Tr(UZ L. ZUT) Tr(UZ'L,ZU)) (subject to UU = I) in order to learn linear projection U.
We extend GLEN to EASE to learn the linear projection U by minimizing log det L., ZUT) log det(UZ (UZ T L, (subject to UU I. We also apply the Sp norm instead of log det. Table shows the results of EASE based on the LogDet and the Sp-norm based relaxations of GLEN. For the simplicity of experiment, we use soft k-means rather than Sinkhorn k-means as the EASE pipeline. Please refer to EASE [54] for the experimental setup of one-shot learning.
We evaluate our approach four few-shot classification benchmarks, mini- Mini-emmaeNet [38], tiered- ImageNet [32], CUB [41], and CIFAR-FS [21]. The performance numbers are given as accuracy % and the 0.95 confidence intervals are reported. We use publicly available pre-trained ResNet- 12 [29] that are trained on the base class training set.
Table 6: Few-shot learning in the transductive setting on EASE based on GLEN.
methods
mini-Imagenet [38]
liered-Imagenet [32] CIFAR-FS [21] CUB [41]
EASE [54]
58.2++0.19
70.9+-0.21
65.2=0.21
77.7=0019
EASE GLEN (S, norm)
60.5+0.23
74.8
67.8=0.25
81,5=0.25
EASE GLEN (LogDet) 61.4:10.23
76.4-1.0.5
69.2-0.25
03,4+0.25
Scalability. GraphSAGE and DGI require neighbor sampling with redundant forward/backward steps (long runtime). In contrast, GLEN-S enjoys a simple implementation with low memory usage/low runtime. For graphs with over 100 thousands nodes and 10 millions edges (Reddit), GLEN runs fast on NVIDIA 1080 GPU. Even on larger graph benchmarks, GLEN is fast as optimizes the total scatter and the within-class matrices whose size depends on embedding size rather than the node number. The runtime of GLEN-S is also favourable in comparison to multi-view augmentation-basse GraphCL.SSeecffcallly GLEN-S'GC took 0.54s, 0.3s, 5.3s and 15.4s on Cora, Citeseer, Pubmed and Cora Full, respectively. GraphCL took 1 110. 19s, 101.0s, 2 8h and 8h respectively. Although the LogDet difference is somewhat slower than the trace difference in forward/backward propagation, it converges faster, thus enjoying similar low runtime.
Conclusions
In this paper, we model contrastvie learning as a rank difference problem to approximate the condition that the rank of total scatter matrix should equal the sum of ranks of within-scatter and between-scatter matrices. We relax this NP-hard assumption with differentiable difference of LogDet terms. We also show two perspectives on GLEN and the existing methods based on the low-rank optimization and distance between symmetric positive (semi- )definite matrices matrices. In low-rank optimization, we explain why the LogDet difference is better surrogate function optimize rank difference compared to the trace difference. We also show that our solution encourages lincar kernel of embeddings become the geometric mean between the total scatter matrix and the within-class matrix. GLEN works well with many backbones outperforming many unsupervised, contrastive and (semi-)supervised methods.
Acknowledgments and Disclosure of Funding
We thank 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. Piotr Koniusz is supported by CSIRO's Machine Learning and Artificial Intelligence Future Science Platform (MLAI FSP).
10

---

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 21-29, 2019.
[2] Philip Bachman, R Devon Hjelm, and William Buchwalter. Learning representations by maximizing mutual information across views. arXiv preprint arXiv:/906.00910 2019.
[3] Mikhail Belkin and Partha Niyogi. Laplacian cigenmaps for dimensionality reduction and data representation. Neural computation, 15(6): 1373-1396, 2003.
[4] Aleksandar Bojchevski and Stephan Günnemann. Deep gaussian embedding of graphs: Unsu- pervised inductive learning via ranking, arXiv preprint #rXXv:170.0088/1 2017.
[5] Hongyun Cai, Vincent W Zheng, and Kevin Chen-Chuan Chang. A comprehensive survey of graph embedding: Problems, techniques, and applications. IEEE Trunsactions on Knowledge and Data Engineering. 3009):6166-1677, 2018.
[6] C Deng, Z Zhao, Y Wang, Z Zhang, and Z Feng. Graphzoom: A multi-level spectral ap- proach for accurate and scalable graph embedding. In International Conference on Learning Representations, 2020.
[7] Maryam Fazel, Haitham Hindi, and Stephen P Boyd. Log-det heuristic for matrix rank mini- mization with applications hankel and euclidean distance matrices. Proceedings of the 2003 American Control Conference, 2003., volume 3, pages 2156-2162. IEEE, 2003.
[8] Donald Geman and Chengda Yang. Nonlinear image recovery with half-quadratic regularization. IEEE transactions on Image Processing, 4(7):932-946, 1995.
[9] 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.
[10] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. In Advances in Neural Information Processing Systems, pages 1024-1034, 2017.
(11) Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi-view representation learning on graphs. In International Conference on Machine Learning, pages 41 4116-4126, 2020.
[12] Xiaofei He and Partha Niyogi. Locality preserving projections. Advances in Neural Information Processing Systems, 16(16):153-16) 2004.
[13] Devon Hjelm, Alex Fedorov, Samuel Lavoie Marchilnnr Karan Grewal, Phil Bachman, Adam Trischler, and Yoshua Bengio. Learning deep representations by mutual information estimation and maximization. arXiv preprint arXiv:1808 (at.:/0088000000 2018.
[14] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning graphs. arXiv preprint arXiv:2005.0063 2020.
[15] Qian Huang, Horace He, Abhay Singh, Ser-Nam Lim, and Austin Benson. Combining label propagation and simple models out per-porforms graph neural networks. In International Conference on Learning Representations 2021.
[16] Zhao Kang, Chong Peng, and Qiang Cheng. Robust pea via nonconvex rank approximation. In 2015 IEEE International Conference on Data Mining, pages 211-220. IEEE, 2015.
[17] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks, arXiv preprint (ate:::699090000 2016.
[18] Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint arXiv:1611.07308, 2016.

---

[19] Piotr Koniusz. Lei Wang, and Anoop Cherian. Tensor representations for action recognition. IEEE Trans. Pattern Anal. Mach. Intell., 44(2):648-66) 665, 2022.
[20] Piotr Koniusz and Hongguang Zhang. Power normalizations in fine-grained image, few- shot image and graph classification. In IEEE Transactions on Puttern Analysis and Machine Intelligence, 2020.
[21] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[22] Brian Kulis et al. Metric learning: A survey, Foundations and Trends@ in Machine Learning, 5(4):287-364, 2013.
[23] Omer Levy and Yoav Goldberg. Neural word embedding as implicit matrix factorization. Advances in Neural Information Processing Systems, 27:2177-2185, 2014.
[24] Guohao Li, Chenxin Xiong, Ali Thabet, and Bernard Ghanem. Deepergen: All you need to train deeper gens. arXiv preprint arXiv:2006.07739 2020.
[25] 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.
[26] Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. Efficient estimation of word representations in vector space. arXiv preprint arXiv: 1301.388,,,,. 2013.
[27] 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.
[28] Karthik Mohan and Maryam Fazel. Iterative reweighted algorithms for matrix rank minimization. The Journal of Machine Learning Research, 13(1):3441 -3733, 2012.
[29] Boris N Oreshkin, Pau Rodriguez, and Alexandre Lacoste. Tadam: Task dependent adaptive metric for improved few-shot learning. arXiv preprint 1rXiv:1805.10123, 2018.
[30] S Pan, R Hu, G Long, J Jiang, I. Yao, and C Zhang. Adversarially regularized graph autoencoder for graph embedding. In International Joint Conference on Artificial Intelligence, 2018.
[31] Bryan Perozzi, Rami Af-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.
[32] Mengye Ren, Eleni Triantafillou, Sachin Ravi, Jake Snell, Kevin Swersky, Joshua B Tenen- baum, Hugo Larochelle, and Richard S Zemel. Meta-learning for semi-supervised few-shot classification. arXiv preprint 18Xiv:1803.0063 00676, 2018.
[33] Emanuele Rossi, Fabrizio Frasca, Ben Chamberlain, Davide Eynard, Michael Bronstein, and Federico Monti. Sign: Scalable inception graph neural networks. arXiv preprint arXiv:2004. /198, 2020.
[34] Ke Sun, Piotr Koniusz, and Zhen Wang. Fisher-bures adversary graph convolutional networks. Conference on Uncertainty in Artificial intelligence, 115:465-475, 2019.
[35] 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.
[36] Joshua B Tenenbaum, Vin De Silva, and John C Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500) 2000.
[37] Petar Velickovic, William Fedus, William Hamilton, Pietro Lio, Yoshua Bengio, and Devon Hjelm. Deep graph infomax. In International Conference Learning Representations, 2019.
12

---

[38] Oriol Vinyals, Charles Blundell, Timothy Lillicrap, Koray Kavukcuoglu, and Daan Wierstra. Matching networks for one shot learning. arXiv preprint arXiv: 600,000000 2016.
[39] Tongzhou Wang and Phillip Isola. Understanding contrastive representation learning through alignment and uniformity the hypersphere. In International Conference on Machine Learning, volume 119, pages 9929-9939, 2020.
[40] Zhengyang Wang and Shuiwang Ji. Second-order pooling for graph neural networks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020.
[41] Peter Welinder, Steve Branson, Takeshi Mita, Catherine Wah, Florian Schroff, Serge Belongie, and Pietro Perona. Caltech-ucsd birds 200. 2010.
[42] Felix Wu, Tianyi Zhang, Amauri Holanda de Souza Jr, Christopher Fifty, Tao Yu, and Kilian Q Weinberger. Simplifying graph convolutional networks. arXiv preprint arXiv: arXiv:1902.000 1902.07133, 2019.
[43] Shuicheng Yan, Dong Xu, Benyu Zhang, Hong-jiang Zhang, Qiang Yang, and Stephen Lin. Graph embedding and extensions: A general framework for dimensionality reduction. IEEE Transactions on Pattern Analysis and Machine Intelligence, 29-5):00-5,, 2007.
[44] 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 1666-16766 2020.
[45] Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi semi-supervised learning with graph embeddings. In International Conference on Machine Learning, pages 40-48, 2016.
[46] Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. Advances Neural Information Processing Systems, 33:5812-5823, 2020.
[47] 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.
[48] Xiaotong Zhang, Han Liu, Qimai Li, and Xiao-Ming Wu. Attributed graph clustering via adaptive graph convolution. arXiv preprint 1rXiv:190..01210. 2019.
[49] Yifei Zhang, Hao Zhu, Ziqiao Meng. Piotr Koniusz, and Irwin King. Graph-adaptive rectified linear unit for graph neural networks. In TheWebConf (WWW), pages 1331-1339. ACM, 2022.
[50] Yifei Zhang, Hao Zhu, Zixing Song, Piotr Koniusz, and Irwin King. COSTA: covariance- preserving feature augmentation for graph contrastive learning. In KDD), pages 2524-2534. ACM, 2022.
[51] Xucbin Zheng, Bingxin Zhou, Junbin Gao, Yuguang Wang. Pictro 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-12771, 2021.
[52] Hao Zhu and Piotr Koniusz. REFINE: Random range finder for network embedding. ACM Conference on Information and Knowledge Management, 2021.
[53] Hao Zhu and Piotr Koniusz. Simple spectral graph convolution. In International Conference on Learning Representations, 2021.
[54] Hao Zhu and Piotr Koniusz. EASE: Unsupervised discriminant subspace learning for transduc- tive few-shot learning. In Proceedings of the IEEE/CV Conference on Computer Vision and Pattern Recognition, pages 9078-9088, 2022.
[55] Hao Zhu, Ke Sun, and Piotr Koniusz. Contrastive laplacian eigenmaps. Advances in Neural Information Processing Systems, 34, 2021.
13

---

[56] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep graph contrastive representation learning. arXiv preprint arXiv:2006. 04100, 2020.
[57] 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

---

Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes], [No], , or [N/A] - You are strongly encouraged to include justification your answer, either by referencing the appropriate section of your paper or providing a brief inline description. For example:
Did you include the license to the code and datasets? [Yes] See Section ?.
Did you include the license the code and datasets? [No] The code and the data are proprietary.
Did you include the license to the code and datasets? [N/A]
Please do modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below,
i. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
ii If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
iii. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
iv. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
v. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "Iimyw9XR2O1", "reviewer": "Reviewer_bffF", "summary": "This paper proposes a novel graph-embedding framework, which is a rank difference model. This rank model is NP-hard to solve, so the authors optimize the loss formulation by means of the logdet. The transformed model is then solvable and proven to be theoretically effective. The paper also offers connection between the given model and other graph embedding methods, and calculate the upper and lower bound of the proposed loss function. In total, the paper is well written and theoretically innovative.", "questions": "1. Can authors give the proof for the Proposition 1? This proposition lacks the necessary proof.\n2. Are there any other cases except COLES that can be generalized to GLEN? If so, please supply examples of these cases. Otherwise, what’s the meaning of the ‘generalization’ of GLEN? \n3. Is the logdet to solve the rank problem the original work of the paper? If not, listing the references is necessary. Does the logdet framework still hold the generalization property？If so, please give the proof.\n4. Is there any other effective methods to solve the rank difference problem? The authors should compare these methods and explain the reason why logdet is chosen. \n", "limitations": "The generalization of the proposed framework is not clearly described,  and many other cases need to supply except COLES. Besides, there are other methods to solve the rank difference problem except using logdet. The paper does not list and compare these methods. ", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength\n1. The COLES can be the special case for the proposed GLEN framework, and the GLEN outperforms the COLES.\n2. The theoretical analysis gives the upper and lower bound of the proposed GLEN, which makes the model have good interpretation.\n3. The experiments are effective to demonstrate the proposed framework does have good performance.\n\nWeakness\n1. It is not clear about the relationship between the proposed model and the contrastive learning, although the contrastive learning is introduced in related work.\n2. Compared with the trace model in COLES, the generalization of the proposed rank difference framework is not illustrated clearly. The author should give proof how the trace model can be generalized into the rank model as a special case. \n3. Although GLEN is called the generalized Laplacian Eigenmaps framework, the paper shows no other cases that can also be generalized to GLEN except COLES.\n4. The paper does not compare the logdet model with other methods that can serve as a surrogate of the rank problem. There are many methods can be used to solve the problem at present, so the authors should list and compare these methods and explain why the logdet is chosen. \n5. The logdet terms are chosen to solve the rank model, which actually transfers the rank model into a logdet model. Does the logdet model still maintain the generalization property? If so, please give the proof.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "427K1wlrPCx", "reviewer": "Reviewer_3VJW", "summary": "The paper proposes a novel objective for graph embedding, called Generalized Laplacian EigeNmaps (GLEN), to learn graph representation by maximizing the difference of logdet between the total scatter matrix and the within-class scatter matrix. The authors interpret this as a surrogate of rank difference maximization and give some theoretical results. Experiments show that GLEN offers good accuracy and scalability against state-of-the-art baselines on various benchmarks.\n\n** Post Rebuttal Update **\n\nI've read the rebuttal and the other reviewers' comments. I appreciate the update the authors have made, for example, the (supposedly) new experimental updates regarding Reviewer bffF's comment. I appreciate the experimental results against the prior art. My general concern is whether the theorem indeed shows a difference from the prior art. It seems to me that the rank difference formulation or the minimum class separation has been identified in the literature. What's more interesting is to explain why the logdet can be a better objective, which seems quite possible given the new experimental results.\n\n\n", "questions": "Q1. The motivation of Condition 1 is unclear. In particular, why $\\text{Rank}(S_t)=\\text{Rank}(S_w)+\\text{Rank}(S_b)$ yields good embedding?\n\nQ2. Why formulate the main problem as rank difference? Why not directly analyze the logdet difference?\n\n", "limitations": "The authors didn't discuss the limitation and potential social impact.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "** Strengths **\n\nS1. The proposed algorithm is based on the scatter matrices, which are of the size of $d\\times d$, not $n\\times n$. Note that $d$ and $n$ are the embedding dimension and the node number, respectively. Thus, the method is quite scalable to large graphs.\n\nS2. Experiments show strong results in various settings and datasets.\n\n** Weaknesses **\n\nW1. The authors approximate the rank difference with logdet difference. However, it is unclear why optimizing the rank difference or the logdet difference leads to good results.\n\nW2. The notations are confusing and may contain errors. For example, in section 3.1, it seems that $Z$ is $d\\times n$ instead of $n\\times m$. Also, the $S$ matrices should be $d\\times d$ instead of $n\\times n$. If $Z$ is $n\\times m$ and $S$ is $n\\times n$, then the algorithm should not be scalable as $n$ is the number of nodes.\n\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "0LKFYg6ifJc", "reviewer": "Reviewer_Vcae", "summary": "This paper proposes a new unsupervised representation learning method, mainly based on GNN. \n\nThe idea is motivated by the scatter matrices that are usually used in LDA. Based on the fact that the features would be discriminative provided that Condition 1 holds, the model aims to maximize rank($S_w$) and minimize rank($S_b$) simultaneously, which is different from the losses of the popular contrastive learning.  \n\nIn Section 3, the authors show that the equivalence between the specific two-layer (featureless) GAE and linear (featureless) GAE. \n\nIn Section 4, the authors try to investigate the real impact of ReLU on the hidden layer. \n\nThen, as the original goal is NP-hard, a surrogate that approximates the rank better than the classical nuclear norm is introduced.  \n\nFinally, sufficient experiments are conducted to verify the idea.  \n\n", "questions": "(More details can be found in the previous part)\n\n1. Why do you constrain the model on the GNNs? In other words, why not conduct experiments on the general datasets?> \n\n2. Is there a difference between the following literature [1] and this paper? It limits the novelty of the paper. \n\n   [1] Calibrated Multi-Task Learning, SIGKDD, 2018.   \n\n3. Could the authors also provide some experiments under the common settings of Cora/Citeseer/PubMed, instead of the random split? ", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Pros: \n\n1. The idea to use the scatter matrices to learn discriminative features seems novel. It is different from the popular contrastive models.  \n2. The motivation is convincing and interesting to me.  \n3. The experimental results, especially on semi-supervised node classification when labels are pretty rare, seem to show effectiveness. \n\n### Cons: \n\n1. An important question that confuses me is why not to testify the idea on the setting of general contrastive learning.  If I don't misunderstand the model, the graph (*i.e.*, adjacency) seems to be only used in the implementation of $f_\\Theta$, which indicates that $f_\\Theta$ could be any neural networks (or other projection techniques).  So why do you constrain the model on the GNNs? If some similar ideas have been proposed in the general contrastive learning (which I'm not familiar with the newest publications), it will severely affect the novelty. \n\n2. A major concern is the surrogate may be not novel. The idea to use $\\log(\\cdot)$ to replace the $\\ell_p$-norm (which is equivalent to the Schatten-$p$ norm for the rank) has been well studied. Is there a difference between the following literature and this paper? It limits the novelty of the paper. \n\n   [1] Calibrated Multi-Task Learning, SIGKDD, 2018.   \n\n3. Could the authors also provide some experiments under the common settings of Cora/Citeseer/PubMed, instead of the random split? It is also an important comparison with the existing GNN models.\n\n4. No source code is provided so that it may limit the reproducibility. \n\n5. There are some typos including but not limited to: \n   - The meaning of letters in boldface is confusing. For example, in Figure 1, the matrix is denoted by $S_b$ while in Section 3.1, all matrices are highlighted by boldface (*e.g.*, $\\textbf{S}_w$). In Line 135，$C$ is also bold.\n   - In Line-145, Theorem 2 -> Theorem 1?\n\nOverall, I would like to update my score after reading other reviews and the response. ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}]

Author rebuttal:

Decision: Accept