Graph Contrastive Learning with Stable and Scalable Spectral Encoding
Authors: Deyu Bo
Yuan Fang
Yang Liu
Chuan Shi
Venue: NeurIPS 2023 poster (2023)
Keywords: Graph Contrastive Learning
Spectral Embedding
TL;DR: We propose an informative, stable, and scalable spectral encode for spatial-spectral graph contrastive learning

Abstract: Graph contrastive learning (GCL) aims to learn representations by capturing the agreements between different graph views. Traditional GCL methods generate views in the spatial domain, but it has been recently discovered that the spectral domain also plays a vital role in complementing spatial views. However, existing spectral-based graph views either ignore the eigenvectors that encode valuable positional information or suffer from high complexity when trying to address the instability of spectral features. To tackle these challenges, we first design an informative, stable, and scalable spectral encoder, termed EigenMLP, to learn effective representations from the spectral features. Theoretically, EigenMLP is invariant to the rotation and reflection transformations on eigenvectors and robust against perturbations. Then, we propose a spatial-spectral contrastive framework (Sp$^{2}$GCL) to capture the consistency between the spatial information encoded by graph neural networks and the spectral information learned by EigenMLP, thus effectively fusing these two graph views. Experiments on the node- and graph-level datasets show that our method not only learns effective graph representations but also achieves a 2--10x speedup over other spectral-based methods.

Graph Contrastive Learning with Stable and Scalable Spectral Encoding
Deyu Bo'r, Yuan Fang", Yang Liu', Chuan Shilt
Beijing University of Posts and Telecommumications, China "Singapore Management University, Singapore (bodeyu, liuyangjanet, shichuan -ubupt. edu. en, yfangdemu. edg.e..ueedd..ggggg......
Abstract
Graph contrastive learning (GCL) aims learn representations by capturing the agreements between different graph views. Traditional GCL methods generate views in the spatial domain, but has been recently discovered that the spectral domain also plays a vital role in complementing spatial views. However, existing spectral-based graph views either ignore the eigenvectors that encode valuable positional information, or suffer from high complexity when trying to address the instability of spectral features. To tackle these challenges, we first design informative, stable, and scalable spectral encoder, termed EigenMLP, to learn effective representations from the spectral features. Theoretically, EigenMLP is invariant to the rotation and reflection transformations on eigenvectors and robust against perturbations. Then, we propose a spatial-spectrac contrastive framework GSp*GCL) capture the consistency between the spatial information encoded by graph neural networks and the spectral information learned by EigenMLP, thus effectively fusing these two graph views. Experiments the node- and graph-level datasets show that our method not only learns effective graph representations but also achieves 20x speedup over other -hastel-bbsed methods.
1 Introduction
Graph neural networks (GNNs) have become the de facto framework to encode graph-structured However, training high-quality GNNs usually requires large number of domain- specific labels, which not feasible in many real-world applications. Therefore, as a paradigm of self-supervised learning, graph contrastive learning (GCL) is proposed to learn node graph
data [14] 35 39..
representations without using labels 220 19 12 38).
Typically, GCL methods first generate different views of a graph, and then contrast the positive views against the negative ones. By minimizing a contrastive loss, GCL methods can learn invariant information from different views for various downstream tasks. Therefore, how to generate ideal graph views is crucial to GCL. Most graph views are obtained by augmenting graphs in the spatial domain, such dropping nodes and edges, heuristically [49 44 g or adversarially [27 40 41). Nevertheless, recent studies [8] argue that spatial perturbations ignore the structural properties, and propose to perturb graph spectrum in the spectral domain.
Generally, the spatial and spectral views represent different information of the graph. The spatial domain captures the feature information and learns local graph representations by propagating the node features along local topology, i.e., k-hop subgraphs. In contrast, the spectral domain covers the global structural information. The eigenvalues and eigenvectors encode the global shapes [3] and
"This work was done when the first author was a visiting student at Singapore Management University t Corresponding author
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Leveraging the agreements between the spatial and spectral views can significantly improve the expressive power and generalization ability of GNNs [37 47 However, several reasons hinder the study of spectral view: First, the spectral features are unstable. Previous work [24] shows that randomly flipping the signs or rotating the coordinates of eigenvectors also satisfies the eigenvalue decomposition, a.k.a., the sign and basis ambiguity issues, implying that spectral features are not unique and hard to transfer [15] 37 Besides, perturbing spectral features is time-consuming. Existing spectral-base -aaed methods [18 17 need to decompose and reconstruct the adjacency matrix, in which the complexity is cubic and quadratic in the number of nodes, respectively,
node absolute positions 225
Therefore, to realize the spatial- contrast, it is natural to ask: How to encode the spectral view of graph effectively and efficiently? To answer this question, we first propose a spectral encoder. named EigenMLP, which not only inherits the scalability advantage of multilayer perceptrons (MLP), but also adheres to two key design principles. First, FigenMI.P resolves the sign ambiguity issue by taking both positive and negative eigenvectors as input. Second, to address the basis ambiguity issue, the weights of EigenMLPP are generated by learnable mapping of the eigenvalues, making them equivariant to the coordinates of eigenvectors. To integrate the representations learned from the spatial and spectral views, we propose a Spatial -ppettal GCL framework GSp*GCL) to maximize the agreements between views and learn effective representations for downstream tasks.
The contributions of our paper are as follows. (1) We propose EigenMLP, a novel spectral encoder to effectively and efficiently learn sign- and inssriinvariant representations from spectral features. (2) We theoretically prove that EigenMLP is permutation -uuutiiiinniiiiiiintt... rotation- and reflection-invariinn and can learn more stable representations against structural perturbations. (3) We propose SpLGCL a spatial-spectral GCL framework that utilizes the cross-domain contrasts to effectively fuse the feature and structural information learned by spatial GNNs and EigenMLP. (4) Extensive experiments on both node-level and graph-level tasks demonstrate the effectiveness of the proposed framework Sp"GCL, and verify the scalability and stability aspects of EigenMLP.
2 Related Work
Graph Contrastive Learning. Most GCL methods aim to learn invariant information by max- imizing the mutual information between different graph views [I 36). There are many ways to generate graph views and we broadly categorize them into the spatial and spectral approaches. In the spatial domain, graph views are usually generated by augmenting the original graphs. For example, GRACE 48, GCA 49 and CCA-SSG 44 propose to augment graphs by randomly dropping edges 27 leverages adversarial training to filter unimportant edges, and JOAO [41 combines different augmentation strategies automatically. While in the spectral domain, the views are generated by perturbing graph spectrum. For example, MVGRL ( heuristically uses a graph diffu- sion as augmentation, which acts as low-pass filter, SpCo 18] proposes preserve low-frequency components and perturbs high-frequency ones, and SPAN 17 generates augmentations by maximiz- ing the spectral change. Besides, SFA (46) analyzes the spectrum of node representations, which is out of the scope of this work. In general, spectral views of graphs may have better performance and interpretability than spatial views but also suffer from high complexity.
and nodes, AD-GCL
Perturbing the graph spectrum is time-consuming. Another approach is to encode the eigenvalues and eigenvectors instead of the eigenspaces. However. cigenvectors suffer from sign and basis ambiguity issues, and using these features directly will affect the stability of the model. Therefore, some spectral encoders are proposed to learn invariant representations from the non-unique spectral features. For example, SAN [15] uses Transformer-based (34) encoder, which
Spectral Encoder:
invariant to the order of the bases. BasisNet [6] uses IGN 21 to learn permutation iinnaaaaionnnnaariant
representations from the eigenspaces. PEG 37 leverages the distance between eigenvectors to reweigh the graph structure and avoids sign and basis ambiguity. However, the complexity of SAN and BasisNet is quadratic, which is difficult to scale to large graphs.
3 Preliminaries
Assume that g = (V.E) E) is a graph, where V is the node set with |V| = N and È is the edge set with |||= = E. Let A E {0, N be the adjacency matrix, and X E R N xxd be the node feature matrix
on G. The normalized graph Laplacian L of G is defined as L I, D AD- where I, is the
N x N identity matrix and is the degree matrix with D; = Σ, A. for E V and Dij = 0 for
i * j. The eigenvalue decomposition (EVD) of graph Laplacian is defined as L UAU where A

---

is a diagonal matrix whose diagonal entries 0 S A1 .... ... S AN S are the eigenvalues of L, and
U [u.... uv]] are the corresponding eigenvectors.
worth noting that some cases, randomly flipping the signs and rotating the coordinates of eigenvectors may also satisfy EVD 244,, which we refer as sign and basis ambiguity.
Sign ambiguity. Given pair of eigenvalue and eigenvector (A,, uz), it satisfies Lu, u, and A; = in Lu; ((e,"")e (Uir Uar' ) Therefore, if u, is an eigenvector of L, then - also satisfies EVD, i.e., u, Lu; = (- ((-
Basis ambiguity. If there is high multiplicity in the eigenvalues, i.e., Ap+1 = some > 1, then the corresponding cigenvectors [up+1.--- ... , .uptgl lie in an orthogonal group O(g) ={Q E R2x0 Q QQ 1. Therefore, for any Q E O(g). replacing [up+1.'.. Up+g i,j p
Apto for
with [1++1---- up+g Q also satisfies EVD, i.e., Lu, X, p
The above two facts state that the cigenvectors of graph Laplacian are not unique. Therefore, the model should consider how to learn sign- and basis-invariant representations from spectral features
for better stability and generalization 37 16 15
Proposed Framework: Sp'GCL
In this section, we present the proposed spatial-spectral GCL framework called Sp'GCL. We first give high-level overview on how to represent and contrast the spatial We then introduce the proposed invariant and equivariant spectral view encoder in detail. Finally, we briefly describe the preprocessing, training, and inference processes.
and spectral views of a graph.
4.1 Overview of GCL
Views refer to different perspectives of the same data [30] Unlike previous GCL methods that generate graph views in a single domain, we propose to model the spatial and spectral views separately and further utilize cross-domain contrasts to capture invariant information. Here we first describe how to represent the spatial and spectral views of graphs.
Spatial View represents the explicit connectivity of nodes, which can be denoted as Va (A,X) Through propagating node features along graph substructures, the spatial view can naturally fuse the topology and content information and learn local smooth representations of a graph.
Spectral View indicates the implicit relationships between nodes, which is expressed as V. (A, U). The eigenvalues and eigenvectors encode the geometric information and node positions of the graph topology, which can be seen as global structural information of graph.
Since graphs are non-Euclidean data, it is difficult to directly contrast the spatial and spectral views. Therefore, we need to design suitable encoders to learn different view representations for GCL:
H (A, H. = ((A, U),
where f and g are the encoders of the spatial and spectral views, respectively, and H. H. E Nxd the spatial and spectral representation matrices, respectively. These representations can then be used in contrastive learning to learn invariant information across both domains.
The fundamental idea of contrastive learning is to define the positive and negative pairs, from which the model can capture the self-supervised signals. our framework, we define the spatial and spectral representations of the same node graph positive pairs, and those of different nodes or graphs as negative pairs. For graph-leve contrasts, we additionally use a readout function learn the graph-level representations. Then, two projection heads Pa. Pe representations into the contrastive space:
Rd + Rd are used to transform the
Z, Pa. (H.), Z. PP (H.).
Subsequently, we employ InfoNCE [33, classical contrastive objective function, to maximize the agreements between spatial and spectral representations:
N
2
log
+ log
(3)
x + Σ eladia))
elat + Ejjts (1(d)tt)
3

---

Table 1: Comparison between different spectral encoders.
p(A.)
Information
Stability
Scalability
Methods
EigVal
VigVee
Sign
Basis
Inductive
Complexity
Z/o
Z|e
MLP 34
O(Nkd)
SAN 15
O(NE'A + Nld)
p(Ax)
E
WN
Ele
BasisNet 16
O(NA'+NNK O(Ekd)
PEG 37
Fig
((NTA)
EigenMLP
MLP
Figure I: Schematic illustration of EigenMLP and ML..
Note: Here is the number of cigenvectors, is the period of polynomial, and d is the hidden dimension.
where ( represents the cosine similarity and is the index of nodes or graphs.
Finally, to materialize our contrastive framework Sp²GCL, we must choose or design the encoders f and g for the two views. For the spatial encoder neural network (MPNN), e.g., GraphSAGE 7 or GIN [39], which is widely adopted in previous GCL methods. For the spectral encoder g. which is the emphasis this work, we propose EigenMLP the next part (Section 4.2) based on several key properties. Note that, on the one hand, although MPNNs can learn useful representations, their expressive power bounded by the 1-Weisfeiler-Lehman (WL) test [39]. On the other hand, the spectral view encodes the global information, which can help overcome the limitation of the 1-WL test [5]. Hence, from the perspective of expressive power, the spectral view is also complementary to the spatial view.
directly employ standard message-passing
4.2 Proposed Spectral Encoder: EigenMLP
The spectral encoder is designed to learn stable representations from spectral features. A desirable spectral encoder should have three properties: (1) It can encode both the information of cigenvalues and eigenvectors, which represent different structural information [15] (2) is free of the sign and basis ambiguity issues in spectral features, toward learning stable representations [37]: (3) It scalable to large graphs and has linear or sublinear time complexity. These three properties pose great challenges to the design of spectral encoders. Here we propose EigenMLP, which adopts an MLP-based architecture for scalability and addresses the sign and basis ambiguity problems for stability. Table I summarizes the differences between the proposed EigenMI. .P and existing spectral encoders. Specifically, FigenMLP satisfies all of the three properties above, as we elaborate below.
Scalability. In general, MLPs have demonstrated good scalability and have been widely used in learning graph representations 45 [1 Since EigenMLP employs an MLP-based architecture, it inherits the low complexity and is linear the number of nodes N.
Stability. MLPs sensitive input data, making the outputs vary with respect to the flipping of signs and rotation coordinates eigenvectors. This motivates us to increase the stability of MLP while maintaining high efficiency. We adopt two design principles that enable MLPs to learn sign- and basis-invariant representations. Figure illlstraats the difference between EigenMLP and MLP.
To address the sign ambiguity issue, follow the design of SignNet [16], taking both positive and negative eigenvectors as inputs:
= [=b((()))) + 6(-u:))
where and á are neural networks, [.] is the concatenation operator, and Ú is the sign-invariant eigenvectors. In practice, the sign-invariant neural networks may slow down model convergence. In this case, we resort to some heuristics to determine the sign of the eigenvectors [47].
To solve the basis ambiguity issue, we first observe that each eigenvector has a corresponding eigen- value, and when the coordinates of the eigenvectors are rotated, the positions of the eigenvalues are also displaced. Therefore, if we replace the weights of MI.P with eigenvalues X = [Λ, X2 An
the model will be invariant to the rotation of eigenvectors, Le., UQ(AQ)T UQQ T UX However, directly replacing the learnable weights with fixed eigenvalues is trivial and will greatly
Some details, such the neural networks and omitted for brevity.

---

limit the expressive power of the model. Therefore, we first extend the scalar eigenvalues to their high-dimensional Fourier features (28] The weights of EigenMLP are then decoded from the Fourier features using a learnable matrix:
p()) = [sin A), cos sin())) cos( ... sin (TX), cos( W p
(5)
where T is the period and Wp E 2T is a learnable matrix. Here p()) can be seen as a graph filter and the filtered eigenvalues are equivariant to the coordinates of eigenvectors [2], which can be used learn powerful and rasis-invariant spectral representations:
g(A U) = Ú. P(A).
(6)
where p()) (o(At),p(A)
[] Nxd represents all the filtered eigenvalues. The detailed matrix form of Equation (6) is provided in Appendix C Note that the learnable matrix W shared between different eigenvalues. Therefore, the size of W is independent of the number of eigenvalues but depends on the period T, which reduces the number of parameters in EigenMLP. More discussions can be found in Section[5.2)
Information.
Notably, the invariant layer, i.e., Equation (6. in EigenMLP incorporates both eigenvalues and eigenvectors, which can capture both geometric and positional information.
4.3 Preprocessing, Training, and Inference
It is worth noting that running EVD for full eigenvectors has the complexity O(N'), which is unacceptable for large graphs. Therefore, in the preprocessing, we use the eigenvectors with smallest- k eigenvalues substitute and reduce the complexity (N) Besides, can pre-calculate the rotation- invariantt spectral features V p(A)). Therefore, in the training and inference, EigenMLP has the implementation of MLP. Note that the decomposition is only computed once in the training. Therefore, the overhead of the preprocessing should be amortized by each training epoch.
In training, traditional GCL methods need to compute the message-passsngg twice for different graph views, whose complexity (FF). While in our framework, only the spatial view needs to calculate the mnessage-psssingg and the complexity of spectral view is O(N). Therefore, our framework is faster than others in the training processing. In inference, because we need to calculate the spatial and spectral representations separately, the inference speed is slightly lower than traditional methods. The overheads of training and inference are provided in Section 6.6
5 Deeper Insights
In this section, we provide deeper insights into EigenMLP to understand its effectiveness. Specifically, we prove that EigenMLP is invariant, equivariant, and stable, and can generalize existing spectral augmentations. Besides, we also comment on the connections to previous work.
5.1 Theoretical Results
Theorem 1. EigenMLP equivariant to permutation, and invariant to rotation, and reflection.
Proof. (Permutation) Assume that there are two matrices L(),, (( E R NxN and (() = PL 2T.T. We have L()) = P ( (PU())) such that (())(A)) (2) p(A).
(Rotation) For any rotation matrix Q E O(N), the eigenvectors are rotated as UQ and the corre- sponding Fourier matrix are permuted Q p(A). Therefore, we have UQ Q p()) Up(A).
(Reflection) Following Proposition I in 16,, a continuous function sign-invariant iff it satisfies f(v) h(v) + h(-e). Hence, EigenMLP is invariant to reflection on the signs of eigenvectors. O
Lemma 1. (Lemma 3.4 in (37)) For any positive semidefinite L without multiple eigenvalues, set V the eigenvectors corresponding the smallest k eigenvalues and sorted as 0 < X For any sufficiently small e > 0, there exists a perturbation AL, ||AL]| < é such that
d
min II(V + +VV - VQ 2 0.99 QcO(K)
max 1SiSk
X|||I| F + o(e))
(7)
5

---

Theorem 2. For any sufficiently small e > O, there exists a perturbation AL, | | <
such that
(QEo())) IVV + AV))pda) -Vp(e))le & 0.99T max
1 IsiSh
A | + o(c). (8)
Lemma states that a small structural perturbation will produce changes unbounded from above in non-equivariant spectral features V if there is small spectral gap. Theorem shows that there is finite upper bound on the changes of cquivariant spectral features p(())). Therefore, EigenMLP can learn more stable representations against structural perturbations. We present the proof of Theorem in Appendix A Experiments Section 6.5 further give an empirical justification of Theorem
Proposition 1. EigenMLP generalizes existing spectral augmentations.
Proof. Existing spectral augmentations, such as SpCo [8] and SPAN [17] generate graph views by perturbing the graph spectrum. We assume that there is continuous univariate function 8(.) between the original eigenvalues À and the perturbed eigenvalues X' such that X 5(x;), and the perturbed eigenvalues are still non-negative. Then these spectral augmentations can be represented as:
A' = Uă(A)U = (U8(A)² ) (US(A)
Note that Equation ( is a Fourier series and can approximate any continuous functions. Therefore, the function 8(-) is special case p(-), and EigenMLP can approximate the simplex geometry B2 of the augmentations, i.e. U8(A) thus generalizing existing spectral augmentations.
5.2 Connections to Existing Work
Hypernetworks 6 are class of neural networks used to generate parameters for another network. EigenMLP can be seen as a special case of Hypernetworks, which takes eigenvalues as input and generates equivariant parameters for spectral features. Because Hypernetworks can generate a set of non-shared weights from shared parameters, it can greatly reduce the number trainable parameters. EigenMLP inherits this advantage, and its number of parameters is only related to the period of the Fourier series, rather than the number of eigenvectors. Therefore, EigenMLP is more efficient than other spectral encoders, including vanilla MLP.
Spectral GNNs aim combine the eigenspaces with filtered eigenvalues, i.e., Ei 8(2.)u,u. and EigenMLP used to combine the eigenvectors with filtered eigenvalues, i.e., Ei= ((A:)u, Therefore, both methods choose to use eigenvalue mappings weights to guarantee the equivariance. However, the calculation of eigenspaces has the complexity of O(N?), which is not suitable for large graphs, whereas EigenMLP is more scalable.
6 Experiments
In this section, we conduct three types of experiments, including unsupervised node classification, unsupervised graph prediction, and transfer learning, verify the effectiveness of Sp'GCL. Besides, we also test the stability and time overhead of the proposed method.
6.1 Unsupervised Node Classification
Datasets. In the node classification task, we consider using graphs with different scales to evaluate both the effectiveness and scalability of GCL methods. Specifically, for the small graphs (< 50,000), we use Pubredd [1], Wiki-CS [22], and Facebook (23) datasets. For the large graphs (> 50,000), we
use Flickr 43 ar Xiv and PPI 7 datasets. Additional statistics are provided in Appendix B
Baselines and Setting. We compare our model against wide range of baselines, including semi- supervised GNNs, e.g., GCN [14] and GAT [35], graph self-supervised learning methods, e.g., DGI 36 and BGRL 29 GCL with spatial augmentations, e.g., MVGRL 8 GRACE 48), and CCA- SSG 44, and GCL with spectral augmentations, e.g., SpCo [18] and SPAN [17. For the Facebook dataset, we randomly split the nodes into train/validation/tes data with ratio of 1:1 :8. For other datasets, we use the public splits for fair comparison. We use two-layer GCN as the encoder for

---

Table 2: Node classification transductive and inductive graphs. Mean accuracy (%) standard deviation. Bold indicates the best performance and "-" means out-of-memory or cannot be reproduced.
Small Graphs (Full-Batch)
Large Graphs (Mini-Batch)
Model
Data
PubMed
Wiki-CS
Facebook
arXiv
Flickr
PPI
GCN
A,X, Y
79.0
77.19+0.12
90.65#0.16
71.74+0.29
49.20+0.31
82.28+0.24
GAT
A,X,
79.0=0.3
77.65=0.11
90,47=0.15
71.82=0.23
54,48+0.21
98.85+0.0S
DGI
A. X
76.8+0.6
75.35+0.14 14
84,42=0.43
70.32+0.25
50.59+0.28
63.80+0.20
BGRL
A. X
79.6.0.5
79.98+0.15
89.71=0.35
71.5420.17
51.8710.15
73.63:0..1
MVGRL
X
80.120.7
77.5220.08
87.29=0.28
71.45#0.14 .4
GRACE
X
80.6+0.4
80.14+0.48
89.32=0.40
69.71 17
CCA-SSG
X.
81.0=0.4
78.85+0.32
89.45=0.60
71.21+0.20
51.6640.10
73.3440.17
SpCo
A.X. A
81.5+0.4
79. 19.1640.27
89.98=0.45
SPAN
A,
81.5.0.2
82.13+0.15
SpCGCL
A,
82.3+0.3
79.42+0.19
90.43=0.13
71.83+0.19
52.05+0.33
74.28+0.22
Table 3: Results on the graph-level tasks. The best and runner-up results are highlighted with bold and underline, respectively. means lower the better, and f means higher the better.
Task
Reyression (Metric: RMSF.)
Classification (Metric: ROC-AUCS
Dataset
molesol
mollipo
molfrocsolv
molbace
molbbbp
molctintox
moltox21
molsider
Supervised
1.17320.057
0.75740.018
2.75510.349
72.97=4.00
68.1721.48
88.1412.51
74.9120.51
57.60&1.40
InfoGraph
1.34440.177 178
1.005 023
10.005+4.819
74.74=3.64
66.33+2.79
64.50+5.32
69.74.0.57
60.5440.90
GraphCL
1.272+0.089
0.910=0.016
7.679+2.748
74.32=2.70
1..22+1.89
74.92+4.42
72.40=1.01
61.76+1.. 1.11
MVGRL
1.43220. 145
0.962
9.024#1.982
74.20=2.31
67,24
73.8424.25
70.48=0.83
61. 61.9420.94
JOAO
1.285a0.122 121
0.86510.082
5.13110.722
7..43=1.94
67.6211.29
78.2114.12
71.83a0.92
62.7310.92
AD-GCL
1,217=0.087
0.842#0.00 028
5.150=00624
76.37=2.03
68. 68.24+147
80,77+3:92
71.42=0.73
63.1990095
SPAN
L.18440.022
0,80240.019
4.53140.463
26.74=2.02
69.59:1.34
80.2842.42
72.83x0.62
64,8740.88
SpL
1.235+0.119
0.835+0.026
4.144:0.573
78.76:1.43
68,72+1.53
80.88+3.86
73.06:0.75
64. 64.23+0.96
all datasets and set the hidden dimension d = 512 for all methods. For model, the spatial encoder is the same as baselines, and we additionally use EigenMLP to learn the spectral representation. In the evaluation, we [77. We run all the models 10 times and report the mean accuracy and standard deviation. More details, e.g., optimizers, and hyperparameters, are provided in Appendix B
linear classifier evaluate the performance of all methods, suggested by
Results. From Table 2 can find that SpLGCL consistently outperforms fate-of-the-art baselines on 5 out of 6 datasets, which validates the effectiveness of the proposed spatial- contrastive framework. Meanwhile, spectral-based methods are proven to be more effective than spatial-based methods, suggesting that integrating spectral information into GCL can help models learn better representations. However, it is worth noting that neither SpCo nor SPAN works for large graphs, implying that perturbing graph spectrum cannot be scalable to large-scale datasets. Therefore, the application scenarios of these two graph augmentations are limited. On the contrary, our method can be used for large graphs and can be easily trained in than other spectral-based methods. Additionally, We find that SpLGCL does not perform well in the Wiki-CS dataset. The reason is that the node features dominate the classification results while the graph structure contributes less. Therefore, the spectral view cannot complement the spatial view.
manner, which is more scalable
6.2 Unsupervised Graph Prediction
Setup. We benchmark our model on the OGB graph property prediction task (9, which contains three regression datasets and five classification datasets. We choose a series of competitive GCL methods as baselines, including InfoGraph 266. GraphCL 42 MVGRL [8] JOAO 4I), AD-GCL (27] and SPAN [17]. It is worth noting that SpCo 18 is not designed for graph-level contrastive learning, so we do not compare with it. We use a five-layer GIN
33 with a graph pooling layer as the encoder for all methods. Similarly, we additionally use EigenMLP to encode the spectral view for Sp2GCL We use a linear downstream classifier, e.g., logistic regression model, to evaluate the performance of different GCL methods, as suggested by [27].
7

---

Table 4: Graph transfer learning on the molecular classification tasks. (Metric: ROC-AUC (%) f)
ZINC-2M
Dataset
ВВBР
Tox21
SIDER
Clin'Tox
BACE
HIV
MUV
ToxCast
No Pre-Train
65.8+4.5
74.0=0.8
17.3+1.6
58.0+4.4
70.1
75.3+1.9
71.8+2.5
63.440.6
InfoGraph
68.8+0.8
75.3+0.5
58.4+0.8
69.9+3.0
73.9
76.0:0.7
75.3+2.5
62.7+0.4
GraphCL
69.740.7
73.9+0.7
60.5+0.9
76.0+2.7
75.4+1.4
78.5+1.2
69.8+2.7
62.4:0.6
MVGRL
69.0#0.5
74.5#0.6
62.2+0.6
77.8+2.2
77.2=1.0
77.1=0.6
73.3+1.4
62.6#0.5
JOAO
71.4+0.9
74.3+0.6
60.5+0.7
81.0+1.6
1..
77.5+1.2
73.7=1.0
63.240.5
AD-GCL
70.0+1.1
76.5+0.8
63.3+0.8
79.8+3.5
78.5+0.8
78.3+1.0
72.3+1.6
63.1+0.7
SPAN
70.040.7
78.020.5
64.7+0.5
80.7+2.1
79.920.7
77.840.6
73.8+0.9
64.2+0.4
SpCCCL
70.3+112
78.2+0.6
63.020.6
81.0#1.9
80.0#1.1
78.040.8
74.2+14
64,8+0.5
Table 5: GCLGCL with different spectral encoders. Table 6: Justification of spatial-spectral contrast.
Pubmed
Facebook
Molbace
Pubmed
Facebook
Molbace
EigenMLP
82.3
90.43
78.76
SpCGCL
82.3
90.43
78.76
MLP
82.3
90.22
77.49
GRACE
80.6
89.32
76.45
SAN
78.6
81.52
75.96
+U +UA
81.2
89.85
77.32
BasisNet
77.3
83.87
74.55
81.5
89.79
77.36
Results. Table summarizes the graph prediction performance. Sp2GCL has 4 best and runner-up performances and makes significant improvements on molfreesoly and molbace. Compared with GraphCL and JOAO, which employ multiple spatial augmentations, e.g., edge and node dropping, and feature masking, Sp GCLGCL outperforms them by only using the spectral domain information. This demonstrates the effectiveness of spectral information. Compared with AD-GCL and SPAN, which use adversarial learning find the near-optimal invariant information [3]] SpLGCL only uses the traditional InfoMax principle [ and achieves competitive performance. This shows that the position information of spectral features is crucial to graph representation learning. Besides, in Table 9 show that the efficiency and scalability of Sp SpLGCL significantly outperform adversarial learning.
6.3 Transfer Learning Scenario
Setup. The transfer learning experiments are used to evaluate the generalization ability of GCL methods. We follow the experimental setup deseribed in [IO], which involves pre-training the GCL methods on a large-scale dataset and subsequently fine-tuning the model on downstream datasets to evaluate their ditti--disttibuttinn performance We use the same graph encoder and baseline as the unsupervised graph prediction task. Further details are provided in Appendix B
Results. According to Table 4 Sp"GCL outperforms baselines in out datasets and achieves an average rank of 1.7 across these datasets. Notably, the performance of different methods on different downstream datasets varies greatly, suggesting that the downstream tasks require distinct information for prediction. Nevertheless, spectral information proves to be crucial in the majority of tasks. Furthermore, Sp GCL achieves comparable performance to SPAN, which employs a spectrum- based augmentation for learning graph representations. This observation indicates that Sp²GCL can learn similar spectrums as SPAN. However, our model falls short of InfoGraph, GraphCI., and JOAO on certain datasets due to the limited availability of feature information in the spectral view.
6.4 Ablation Studies
We conducted two ablation studies validate the effectiveness of EigenMLP and the proposed framework, GCLG Initially, we replace EigenMLP with different spectral encoders and evaluate their performance on PubMed, Facebook, and molbace datasets. The results, presented in Tables demonstrate that EigenMLP consistently outperforms other spectral encoders, thus confirming its effectiveness learning spectral representations. Moreover, we aim to justify the superior ability of spatial-spectres contrast in fusing spatial and spectral representations. To accomplish this, we concatenate node features with eigenvectors and eigenvalues and subsequently feed them into GRACE. As shown in Table 6 observe that incorporating spectral features improves the performance in

---

Table 7: Synthetic perturbations: Eigenvectors with random reflection II and rotation Q.
Table 8: Practical perturbations: Eigenvectors with different EVD tolerances.
Test
Test
PubMed
U
UI
UQ
PubMed
Us
U4
Us
78.8 (+0.1)
(-5.5)
(-6.4)
U3
(+0.3)
73.9 (-1.5)
73.7 (-7.8)
Train
U11
78.5 (-7.8)
78.9 (-0.4)
79.0 (-5.2)
Tmin
U,
(-3.2
78.2 (+0.3)
72.8 (-6.8)
UQ
78.7 (-5.1)
78.8 (-9.3)
78.9 (+0.0)
U,
73.7 (-6.9)
(-.00)
79.7 (-0.)
Table 9: Time overheads (s) of different GCL methods.
Table 10: Overall time overheads (s) of different spectral encoders in 1000
Training (100 Epochs)
Inference (x10->)
Method
Preprocessing
forward passes.
GRACE MVGRL (GD)
0.00
22.77
4.4
Method
Facebook (A = 100)
moltox2
898.23
20.01
4.7
(7831 Graphs)
SpCo (SI, T=10)
127.16
22.81
4.5
MLP
2.24
2.09
SPAN (EVD. T=10)
658.62
142.92
SAN
127.23
60.58
BasisNet
169.83
84.64
SpCGCL (EVD)
66.44
17.79
6.2
EigenMIP
5.34
3.14
GRACE. Nevertheless, the performance is still inferior to that of Sp²GCL, thus providing further evidence of the effectiveness of ppatial-ppectral contrast.
6.5 Stability of EigenMLP and MLP
We conduct stability experiments to evaluate whether EigenMLP and MLP can learn stable representa- tions against perturbations. We consider two types perturbations: 1) Synthetic perturbation, which applies random reflection II and rotations Q on the eigenvectors. 2) Practical perturbation, which decomposes the Laplacian matrix with different tolerances (10-3 10-1, 10-5). The corresponding eigenvectors expressed U3. U4, and U5. Note that synthetic perturbation only changes the signs and coordinates of eigenvectors while practical perturbation is more challenging because perturbs the values. For clearer results, only evaluate the performance of spectral representations.
For each type perturbation, we construct three instances, i.e., (U, UII, UQ) or (U3, Ua. Us). The models are trained on one instance and tested on the other two instances on PubMed. We report the results of EigenMLP and show the performance change after switching to MLP the brackets. From Table 7 we can find that the synthetic perturbation can hardly change the representations learned by EigenMLP but has great influence on MIP. Additionally, Table shows that practical perturbations can affect both FigenMLP and MI.P. Nevertheless, HigenMLP still consistently outperforms MI.P across different tolerances, which verifies the stability of EigenMLP.
6.6 Time Overhead
To assess the efficiency, we compare the time overhead of Sp2GCL with other GCL methods as well as compare EigenMLP with different spectral encoders. The time costs associated with preprocessing. training, and inference are shown in Table Previous spectrum-based methods have signíficant time costs in the preprocessing stage, e,g., graph diffusion (GD) or Sinkhorn's 's Iteration (SI), whereas Sp²GCL exhibits minimal overhead. In the training stage, SpLG outperforms other methods due to the efficient spectral encoding, but it also introduces an additional burden during inference. Table TO illustrates the overhead imposed by various spectral encoders within the Sp²GCL framework. Both MLP and EigenMLP exhibit remarkable efficiency. Conversely, SAN and BasisNet entail excessive time costs due to their quadratic time complexity.
Conclusion
In this study, we introduce SpLGCL, novel spatial-spectral GCL framework that learns the con- sistency between the spatial and spectral views of graphs. To effectively and efficiently learn the spectral view information, representations from the non-unique spectral features. Extensive experiments on various graph-related tasks demonstrate the effectiveness,, efficiency, and stability of the proposed method.
propose EigenMLP, scalable spectral encoder to learn stable spectral

---

Limitation and Broader Impact Currently, we focus on encoding spectral features while ignoring node features. A promising future direction is unify these two kinds of information learn effective graph representations. Our work reveals the superiority of integrating spectral information into GCL and may inspire the community to pay more attention the spectral view of graphs.
Acknowledgments and Disclosure of Funding
This work is supported part by the National Natural Science Foundation of China (No. U20B2045, 62192784, U22B2038, 62002029, 62172052). This work is also partially supported by the Ministry of Education, Singapore, under its Academic Research Fund Tier 2 (Proposal ID: T2EP20122-004). Any opinions, findings and conclusions recommendations expressed in this material are those of the author(s) and do not reflect the views of the Ministry of Education, Singapore.
References
[1] Philip Bachman, Devon Hjelm, and William Buchwalter. Learning representations by maximizing mutual information across views. In NeurIPS, pages 15509-15519, 2019.
[2] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In NeurlPS, pages 3837-3845, 2016.
[3] Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. CoRR, abs/2012.0966 2020.
[4] Vijay Prakash Dwivedi, Chaitanya K. Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. CoRR, abs/2003.00982, 2020.
[5] Or Feldman, Amit Boyarski, Shai Feldman, Dani Kogan, Avi Mendelson, and Chaim Baskin. Weisfeiler and leman go infinite: Spectral and combinatorial pre-colorings. CoRR, abs/2201.13410, 2022.
[6] David Ha, Andrew M. Dai, and Quoc V. Le. Hypereeworrss. In ICLR (Poster). OpenReview.ner, 2017.
[7] William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. NIPS, pages 1024-1034, 2017.
[8] Kaveh Hassani and Amir Hosein Khas Ahmadi. Contrastive multi-view representation learning on graphs. In ICML, volume 119 of Proceedings of Machine Learning Research, pages 41 16- 4126. PMLR, 2020.
[9] 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. In NeurIPS, 2020.
[10] Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay S. Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. In ICLR. OpenReview.net, 2020.
[11] Yang Hu, Haoxuan You, Zhecan Wang, Zhicheng Wang, Erjin Zhou, and Yue Gao. Graph-mlp: Node classification without message passing in graph. CoRR, his/2106.04051. 2021.
[12] Wei Jin, Tyler Derr, Haochen Liu, Yiqi Wang, Suhang Wang, Zitao Liu, and Jiliang Tang. Self-supervised learning on graphs: Deep insights and new direction. CoRR, abs/2006. 10141, 2020.
[13] Mark Kac. Can one hear the shape of a drum? The american mathematical monthly, 73(4P2): 23, 1966.
[14] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
10

---

[15] Devin Kreuzer, Dominique Beaini, William L. Hamilton, Vincent Létourneau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. In NewrIPS, pages 21618-21629 2021.
[16] Derek Lim, Joshua Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, and Stefanie Jegelka. Sign and basis invariant networks for spectral graph representation learning. CoRR, abs/2202.13013. 2022.
[17] Lu Lin, Jinghui Chen, and Hongning Wang. Spectral augmentation for self-supervised learning on graphs. In ICLR, 2023.
[18) Nian Liu, Xiao Wang, Deyu Bo, Chuan Shi, and Jian Pei. Revisiting graph contrastive learning from the perspective of graph spectrum. In NeurlPS, 2022.
[19] Xiao Liu, Fanjin Zhang. Zhenyu Hou, Li Mian, Zhaoyu Wang, Jing Zhang, and Jie Tang. Self- supervised learning: Generative or contrastive. IEEE Trans. Knowl, Data Eng., 35(1):857-876, 2023.
[20] Yixin Liu, Shirui Pan, Ming Jin, Chuan Zhou, Feng Xia, and Philip S. Yu. Graph self-supervised learning: A survey. CoRR, 0tss2203.00011., 2021.
[21] Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. ICLR (Poster). OpenReview.net, 2019.
[22] Péter Mernyei and Catalina Cangea. Wiki-cs: A wikipedia-based benchmark for graph neural networks. CoRR, abs/2007.00291,, 2020.
[23] Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. J. Complex Networks, 92),, 2021.
[24] Daniel A. Spielman. Spectral graph theory and its applications. In FOCS, pages 29-38. IEEE Computer Society, 2007.
[25] Balasubramaniam Srinivasan and Bruno Ribeiro. On the equivalence between positional node embeddings and structural graph representations. In ICLR. OpenReview.net, 2020.
[26] Fan-Yun Sun, Jordan Hoffmann, Vikas Verma, and Jian Tang. Infograph: Unsupervised and semi-supervised graph-level representation learning via mutual information maximization. In ICLR. OpenReview.net, 2020.
[27] Susheel Suresh, Pan Li, Cong Hao, and Jennifer Neville. Adversarial graph augmentation to improve graph contrastive learning. NeurIPS, pages 15920-15933, 2021.
[28] Matthew Tancik, Pratul P. Srinivasan, Ben Mildenhall, Sara Fridovich-Keil Nithin Raghavan, Utkarsh Singhal, Ravi Ramamoorthi, Jonathan Barron, and Ren Ng. Fourier features let networks learn high frequency functions in low dimensional domains. In NeurlPS, 2020.
[29] Shantanu Thakoor, Corentin Tallec, Mohammad Gheshlaghi Azar, Mehdi Azabou, Eva L. Dyer, Rémi Munos, Petar Velickovic, and Michal Valko. Large-scale representation learning graphs via bootstrapping. In ICLR. OpenReview.ne,, 2022.
[30] Yonglong Tian, Dilip Krishnan, and Phillip Isola. Contrastive multiview coding. In ECCV, pages 776-794. Springer, 2020.
[31] Yonglong Tian, Chen Sun, Ben Poole, Dilip Krishnan, Cordelia Schmid, and Phillip Isola. What makes for good views for contrastive learning? In NeurIPS, 2020.
[32] Leo Torres, Kevin Chan, and Tina Fliassi-Rad. GLEE: geometric laplacian eigenmap embedding. J. Complex Networks, 8(2), 2020.
[33] Aäron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding, CoRR, abs/1807 007448, 2018.

---

[34] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. In NIPS, pages 9900000. 2017.
[35] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
[36] Petar Velickovic, William Fedus, William L. Hamilton, Pietro Liò, Yoshua Bengio, and R. Devon Hjelm. Deep graph infomax. In ICLR (Poster). OpenReview.net, 2019.
[37] Haorui Wang, Haoteng Yin, Muhan Zhang, and Pan Li. Equivariant and stable positional encoding for more powerful graph neural networks. In ICLR. OpenReview.net, 2022.
[38] Lirong Wu, Haitao Lin, Cheng Tan, Zhangyang Gao, and Stan Z. Li. Self-supervised learning on graphs: Contrastive, generative, or predictive. IEEE Transactions on Knowledge and Data Engineering, 2021.
[39] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In ICLR. OpenReview.net, 2019.
[40] Longqi Yang, Liangliang Zhang, and Wenjing Yang. Graph adversarial self seff-supervised learning. In NeurlPS, pages 14887-14899, 2021.
[41] Yuning You, Tianlong Chen, Yang Shen, and Zhangyang Wang. Graph contrastive learning automated. In ICML, volume 139 of Proceedings of Machine Learning Research, pages 12121-12132. PMLR, 2021.
[42] Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. In NeurlPS, 2020.
[43] Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor K. Prasanna. Graphsaint: Graph sampling based inductive learning method. In ICLR. OpenReview.net, 2020.
[44] Hengrui Zhang, Qitian Wu, Junchi Yan, David Wipf, and Philip S. Yu. From canonical correlation analysis self-supervised graph neural networks. In NeurIPS, pages 76-89, 2021.
[45] Shichang Zhang, Yozen Liu, Yizhou Sun, and Neil Shah. Graph-less neural networks: Teaching old mips new tricks via distillation. In ICLR. OpenReview.net, 2022.
[46] Yifei Zhang, Hao Zhu, Zixing Song, Piotr Koniusz, and Irwin King. Spectral feature augmenta- tion for graph contrastive learning and beyond. In AAAI, 2023.
[47] Ziwei Zhang, Peng Cui, Jian Pei, Xin Wang, and Wenwu Zhu. Eigen-gnn: A graph structure preserving plug-in in for gnns. IEEE Trans. Knowl. Data Eng., 35(3):2544-2555 2555, 2023.
[48] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep graph contrastive representation learning. CoRR, abs/2006.04133 04131,, 2020.
[49] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Graph contrastive learning with adaptive augmentation. In WWW, pages 2069 20800. ACM/ / IW3C2, 2021.
12

---

Appendices
A Proof of Theorem 2
We use to indicate the index of X 1 max A1+1 Aq -1 and perturb graph Laplacian L by perturbing the eigenvectors. Specifically, we set
u =i=vi= u + eu4+1
(1)
1 =- cu; + v1 u,,1
Note that ||u||| || and u² T 11441
0. Therefore, replacing u, and u with uy and 1 still satisfies EVD. We denote V [u,,..., u/, +11 ug]- Then the perturbation can be
represented as AL V'AV" VAVT = >u(u''u (uu!)) + 1 u/+1 T 14414
For sufficient small 0, we have:
min QcO(k)
(I(V + +VV VQ
=||u} ug u u+tilF IF
=Il(V 2 - 1ju; +
1)4441 euillr
-4(1 V1- (2)
-2 + o(E2).
For Fourier features with period T
2 we have:
VQEO()) (I(V + AV)p(As) Vp(Ae)ll
=|1 [u] ug u/41 u (p(A;), ((S+1)) ||
7/2
|| (in)):) - u,) +in((A:))(( u;41)lle
(3)
T/2
Σ coss(M (A:)(A))uu - u.) (os())+))(((+1 u411)lF
S7 (I|ug u; + || 1s+1le))
<2( + o(E2))
Next, we characterize || |LL|E:
| F
A (u/u - -uuu + d4t1 (M/arteer - u
|[ A1) [- (u,u, (7t1 +evI (w.ui Fu ][
(4)
= -Ak+1 - 2t)² (2 (2lluuuT + u +0(2))
-2(A+11-A - (e2 +e())
Combining Equations and ( we have the lower bound of the changes of non-equivariant spectral
features under small perturbations:
|I(V AV) VQ F 0.99 max min QEO(k)
DAet - >. o(e),
1SiSk
which concludes the Lemma [ i.e., Lemma 3.4 37
Combining Equations and 4 we have the upper bound of the changes of equivariant spectral features under small perturbations:
\Qεo()) [[( +
S 0.997
max
A
>||-I| + o(e), (6)
ISiSk
which concludes the Theorem 2
13

---

B Detailed Experimental Setup
In this section, we report the details of our experiments. Specifically, first introduce some general settings in all experiments. Then we introduce the detailed setup of each experiment one by one.
B.1 General Settings
Optimizer.
For all experiments, we use the Adam optimizer.
Environment.
The environment in which we run experiments is:
Linux version: 5.19.0-38-gee -9-0-e8-eenneii
Operating system: Ubuntu 22.04.2
CPU information: AMD EPYC 7313P 16 oo-r Processor
GPU information:
GeForce RTX 3090 (24 GB)
Resources.
The addresses and licenses of all datasets are as follows:
PubMed:
https///gtthhobooo///t/////yy (MIT License)
Wiki-CS: http:///ww.sstaacoo///////o/aaaa (MIT License)
Facebook: http:////ggttttocoo/o///aaeaaaaa (GPL-3.0 license)
arXiv: www.:h/wrrgghhaaooooo///////s/sp
license)
Flickr: httpss//ggttuuucco//rrrpallll/pp (MIT license)
|Ptatprrr/gttttuooooooooarsr//rr license)
license)
ZINC-2M: http://////ggggaaaoooo////aaaaaa
(MIT license)
Reproducibility. Our code attached in the supplementary material.
B.2 Unsupervised Node Classification
Evaluation protocol. In the unsupervised node classification task, all methods first trained with the corresponding self-supervised learning objectives. Then the learned representations are evaluated with Logistic classifier with normalization. We evaluate the method every 10 epochs and the maximum epoch is set to 1000. For the mini-batch training, we set the batch size to 1024. The detailed statisties are shown in Table I and the hyperparameters are shown in Table
Table Statistics of unsupervised node classification datasets.
Graphs
Nodes
Edges
Features
Classes
PubMed
19,717
88,648
500
Wiki-CS
1
11,701
216,123
300
10
Facebook
22,470
342,004
128
arXiv
169,343
1,116.243
128
40
Flickr
89,250
899,756
500
PPI
24
56,928
1,226,368
50
121
B.3 Unsupervised Graph Prediction
Evaluation protocol. In the unsupervised graph prediction task, we use the stand encoder, provided by OGB as the spatial encoder of SpLGCL, which is 5-layer GIN with hidden dimension df 300. We use add pooling to learn graph-level representations and set the batch size to 32, For the spectral
14

---

Table 2: Statistics of unsupervised node classification datasets.
# Eigenvectors (k)
Period (T)
Ir
wd
Dropout
PubMed
30
20
le-3
0
Wiki-CS
100
20
1e-3
0
Facebook
100
20
le-3
arXiv
200
20
le-3
0
Flickr
100
20
le-3
PPI
50
20
1e-3
0
encoder, due the relatively small sizes of the molecular graphs, we use all eigenvectors as the spectral features. We set the learning rate to 0.001 and the period to 10 for all datasets, and the number of training epochs chosen among {20, 50, 80, 100, 150) using the validation set, as suggested by AD-GCL [27]. For the downstream evaluator, we use Riger regressor for the regression tasks and Logistic classifier for the binary classification tasks. The strength of l2 normalization is grid searched among (0.001, 0.01, 0.1, I, 10, 100, 1000) the validation set for each dataset. The detailed statistics of the datasets are shown Table
Table 3: Statistics of unsupervised graph prediction datasets.
Graphs
Avg. Nodes
Avg. Edges
Classes
Task
Metrie
ogbg-molesol
1,128
13.3
13.7
Regression
RMSE
ogbg-mollipo
4,200
27.0
29.5
1
Regression
RMSE
oghg-molfiresoov
642
8.7
8.4
Regression
RMSE
ogbg-molbace
1,513
34.1
36.9
1
Binary Class.
ROC-AUC
ogbg-molbbbp
2,039
24.1
26.0
1
Binary Class.
ROC-AUC
oghg-molclintox
1,477
26.2
27.9
2
Binary Class.
ROC-AUC
ogbg-moltox21
7,831
18.6
19.3
12
Binary Class.
ROC-AUC
oghg-molsider
1,427
33.6
35.4
27
Binary Class.
ROC-AUC
B.4 Transfer Learning
Evaluation protocol. For the transfer learning task, we use same GIN encoder as 10. In the pre-training stage, the learning rate is set to 0.001 and the number of training epochs is chosen from (20, 50, 80, 100) based on the validation set. Similarly, we use cigenvalues and eigenvectors as the spectral features, and the period is set to 10. In the fine-tuning stage, remove the self-supervised learning objective, and an additional linear projection layer is used on the output of the encoder for classification. The hyperparameters are the same in the pre-training stage. The detailed statistics of the datasets are shown Table 4
Table 4: Statistics of transfer learning datasets.
Graphs
Utilization
Avg, Nodes
Avg. Edges
ZINC-2M
Pre-Training 2,000,000
26.62
57.72
BBBP
Finetuning
2,039
24.06
51.90
Tox21
Finetuning
7,831
18.57
38.58
SIDER
Finctuning
1,427
33.64
70.71
Clin
Finetuning
1,477
26.15
55.76
BACE
Finetuning
1,513
34.08
73.71
HIV
Finetuning
41,127
25.51
54.93
MUV
Finetuning
93,087
24.23
52.55
ToxCast
Finetuning
8,576
18.78
38.52
15

---

B.5 Stability Experiment
We use the PyTorch-Seee style pseudo code to explain how we generate the synthetic perturbations (Figure and practical perturbations (Figure 3).
e, u - torch. linalg. eigh(L) EVD
e3, u3 scipy sparse linalg. eigsh
L, k-100, which- 'S', tol-1e-3)
random sign 2+torch. randint (0, 2, (N,))- 1 fflat. f)
sign_flis alpp torch. torch.diag coor flip torch. randperm
e4, scipy sparse linalg.nnii linal.. eigsh(
L, k=100, which='SM tol=1e-4)
u_sign morch.mm(u, sign rign_flip)
e5, scipy sparse linallinggggg eigsh(
u_basis c. coor_flip]
L, k-0, which- 'M', tol=1e-5)
Figure 2: Synthetic perturbations
Figure 3: Practical perturbations
C Matrix Form of EigenMLP
We give detailed matrix form of Equation 6 from which we can see that the Fourier features of eigenvalues give different weights the eigenvectors, thus making the model invariant to the rotation of coordinates and preserving good fitting ability.
coo((1) cos (22)
sin(A1) sin(A2)
cos cos(TM) (T)))
(TA)))
cos (x22)
(in(
coss (x))
sin(Xe)
cos(TAa) sin(TAs))
Eigenvectirs, N x
Fourier features of cigcovalues, x 2T
h
h h1
Lo
2T
02
TT
h2
Patameters of leurnable matrix,
Representations, N X
D Pseudo Algorithm
In order to better demonstrate our algorithm, here we provide the pseudo algorithms of EigenMLP (Figure and SCLGCL (Figure 5).
16

---

Figure 4: Pseudo Algorithm of ELg
class EigenMLP (nn Module)
def
inint_ k, d, T): k: number Eigenvectors hidden dimension
T: period
self .pi mn am.Sequential (in.iaarn.....na d), mn meReLU,, mn. Linear (d, d))
self psi nn Sequential (nn. Linear (d, d) mn ReLUO, nn Linear (d, 1)) self mlp Sequential (nn. Linear (2+T, d), ReLU(,, Linear (d, d))
def forward(e, u)
(-umsqueeze(-1)
self self.pe(ssell phi (u) self phi(-u)) s-ueeze
[N, kc
T_term torch. ar T). f)loatt
T_e e. ummuuueeze
F_e torch. cat ([torch. si_eT_ torch, cos (T_e)), dim--1) # [c, 2T)
return self mlwmtorccc...m..m.oommmm mu, F_e))
Figure 5: Pseudo Algorithm of SC2GCL
def Sp2GCL x, u):
9: graph structures
a: node features
e: eigenvalues
u: eigenvectors
GNN(g, x)
x_e EigenMLP(e, u)
For graph-level tasks a. add (g, a_a) e.e add_pool(g) (g, m_e)
h_a peppojectionneaaddaaa.
h_e (pe_projection__eadxx.. (x_e)
h_a normaalize (h_a, dim=-1, 1, p=2)
h_e normalize(h_e, dim=-1, 2=2)
logits = torch mm (h_a, b_e.
labels torch. arange (h_ size((). (0), dtype=torch long)
return 0.5 prcross_one cosss__entroyy1ooo
labels)
0.5 F. s.cross_enti entoentrrropp (logits... labels)
17


Reviews:
[{"review_id": "jDXOJB1gHY", "reviewer": "Reviewer_9zn6", "summary": "This paper proposes a graph contrastive learning model with spatial and spectral augmentations, with a novel spectral encoder EigenMLP that could address the stability issue from eigen-decomposition. To exploit the strength of spatial and spectral domains, SP2GCL deploys two augmentation views for the contrastive framework; in the spectral view, it introduces tricks to alleviate the ambiguity of signs and basis, in order to stabilize the training process. The performances of node-level and graph-level experiments, as well as the transfer learning tasks, show the advantages of the proposed framework.", "questions": "In the 3rd paragraph of Introduction, it's stated that spatial methods capture local features and so as spectral ones to global features, does it still true for the augmentations? Is it possible that some spectral augmentations merely perturb some kind of edges (such as low-degree or deviant ones)?", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. Contrastive learning for graph data is a prosperous and promising field, especially for the label-sparse settings and for the exploration of properties of non-Euclidean data.\n2. The spectral part in the proposed framework attempts to address the stability and overhead issues, which are the main obstacle in the spectral methods for graphs.\n3. Bridging among the spatial and spectral views is an interesting attempt, which could also make full use of their complementary properties.", "weaknesses": "1. As the authors emphasize the stability of their method, more theoretical and empirical analysis are expected to validate it.\n2. I feel confused about the introduction of Fourier features in Line 169; the reasons and influences of them could be more detailed.\n3. The performances are not always competitive in the experiment section; it may help to explain based on the properties of data sets.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your valuable suggestions!\n\n> **Q1: As the authors emphasize the stability of their method, more theoretical and empirical analysis are expected to validate it.**\n\nA1: Here are the theoretical and empirical analyses:\n1. **Theoretical analysis**: In Section 5.1, we theoretically analyze the stability of our method against structural perturbations. Specifically, Theorem 2 states that the inverse of the spectral gap bounds the change of EigenMLP, while Lemma 1 shows that the change of MLP is unbounded. Therefore, EigenMLP is more stable than MLP. \n\n2. **Empirical analysis**: In Section 6.5, we conduct an experiment to validate the theoretical analysis, where two types of perturbations are used to evaluate the stability of EigenMLP and MLP. Detailed results are shown in Tables 7 and 8.\n\n**To further verify the adversarial robustness**, we conduct a new experiment that injects adversarial edges into the graph structures and tests the performance of Sp2GCL and other GCL methods on the Pubmed dataset. We consider three competitive baselines, GRACE [1], SPAN [2], and SP-AGCL [3].\n\nSpecifically, we consider two graph adversarial attacks, i.e., Nettack [4] and Metattack [5]. To perform a fair comparison, we employ the data generated by Pro-GNN [6]. The training, validation, and testing nodes are randomly divided in a ratio of 1:1:8. The results are shown below, where Sp2GCL consistently learns stable representations against various adversarial attacks, while other GCL methods are more vulnerable.\n\n| | Clean | Nettack ($n=5$) | Metattack ($p=0.2$) | \n:-: | :-: | :-: | :-:\n| GRACE | **85.9±0.1** | 74.5±1.3 ($\\downarrow$13.3%) | 71.4±0.2 ($\\downarrow$16.9%) |\n| SPAN | 81.5±0.3 | 76.4±2.1 ($\\downarrow$6.3%) | 72.7±0.6 ($\\downarrow$10.8%) |\n| SP-AGCL | 85.5±0.3 | 78.1±1.6 ($\\downarrow$8.7%) | 75.1±0.5 ($\\downarrow$12.2%) |\n| Sp2GCL | 83.3±0.5 | **79.1±1.7 ($\\downarrow$5.0%)** | **75.4±0.4 ($\\downarrow$9.5%)** |\n\n[1] Deep Graph Contrastive Representation Learning.\n\n[2] Spectral Augmentation for Self-Supervised Learning on Graphs. ICLR 2023.\n\n[3] Similarity Preserving Adversarial Graph Contrastive Learning. KDD 2023.\n\n[4] Adversarial Attacks on Neural Networks for Graph Data. KDD 2018.\n\n[5] Adversarial Attacks on Graph Neural Networks via Meta Learning. ICLR 2019.\n\n[6] Graph Structure Learning for Robust Graph Neural Networks. KDD 2020.\n\n> **Q2: I feel confused about the introduction of Fourier features in Line 169; the reasons and influences of them could be more detailed.**\n\nA2: Before introducing the role of Fourier features, we first explain the role of eigenvalues. Eigenvalues are instrumental in addressing the basis-ambiguity issue as they are equivariant to the rotation of eigenvectors, i.e., $\\mathbf{U}\\mathbf{Q} \\cdot (\\Lambda\\mathbf{Q})^{\\top} = \\mathbf{U} {\\Lambda}^{\\top}$, where $\\mathbf{Q}$ is the random rotation matrix.\n\nNotably, the raw eigenvalues tend to assign greater significance to higher frequencies. However, in practice, low-frequency information also wields considerable importance [7]. Employing raw eigenvalues falls short of attaining optimal results. To overcome this limitation, it becomes necessary to learn a set of new eigenvalues to reweight the eigenvectors.\n\nIn this paper, we choose to learn new eigenvalues from the Fourier features of the raw eigenvalues, i.e., $λ_{new}=[\\sin(λ), \\cos(λ), ..., \\sin(Tλ), \\cos(Tλ)]\\mathbf{W}$. This design has been widely used in other fields. For example, Transformer uses positional encoding to preserve the order information of input tokens [8].\n\nThe advantages of Fourier features are two-fold:\n- Fourier features provide a multi-scale representation of scalar eigenvalues and let neural networks learn high-frequency information [9].\n- Fourier features are bounded in [-1, 1], which are more stable than other methods, such as polynomials.\n\n[7] Revisiting Graph Neural Networks: All We Have is Low-Pass Filters.\n\n[8] Attention Is All You Need. NeurIPS 2017.\n\n[9] Fourier Features Let Networks Learn High Frequency Functions in Low Dimensional Domains. NeurIPS 2020.\n\n> **Q3:The performances are not always competitive in the experiment section; it may help to explain based on the properties of data sets.**\n\nA3: In some chemical datasets, the performance of EigenMLP drops slightly. This may be due to the fact that the properties of the molecule are determined by some important substructures [10] rather than the global structure. However, eigenvectors encode the global position information and are not good at modeling substructures. A possible solution is to use data augmentation to mask some nodes and obtain the eigenvectors of subgraphs.\n\n[10]  Convolutional networks on graphs for learning molecular fingerprints. NeurIPS 2015.\n\n> **Q4: Does it still true for the augmentations? Is it possible that some spectral augmentations merely perturb some kind of edges (such as low-degree or deviant ones)?**\n\nA4: We think this statement still holds for graph augmentations. According to the definition of eigenvalue decomposition, the graph structure is composed of different eigenspaces, i.e., $\\mathbf{A}=\\mathbf{U} \\Lambda \\mathbf{U}^{\\top} = \\sum \\lambda_{i} u_{i} {u_{i}}^{\\top} $.\nBecause the eigenvector $u_{i}$ is a dense vector, the induced eigenspace $u_{i} {u_{i}}^{\\top}$ is a dense matrix. Therefore, a small perturbation in the eigenvalues will result in a global change in the graph structure, i.e., $\\Delta \\mathbf{A} = \\Delta \\lambda_{i} u_{i} {u_{i}}^{\\top}$."}, {"review_id": "mvNVLqxlxI", "reviewer": "Reviewer_xYrm", "summary": "In this paper, the authors propose eigenMLP,an informative, stable, and scalable spectral encoder, which is invariant to the rotation and reflection transformations on eigenvectors and robust against perturbations. Based on eigenMLP,  spatial-spectral contrastive framework is proposed to capture the consistency between the spatial information and spectral information. ", "questions": "1. What is the T in Eq.8?\n\n2. EigenMLP is able to outperform other spectral-based GNNs with the usual semi-supervised setting? \n\n3. Why the MLP is so close to EIgenMLP in Table 5? ", "limitations": "N/A", "rating": 5, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The eigenMLP is very motivated. The motivation and the theoretical analysis are convincing.\n\n2. Based on eigenMLP, the spectral augmentation is bounded by pertubation delta L.\n\n", "weaknesses": "There are some major issues:\n1. I think the eigenMLP is the main contribution but I don't know why the authors try to highlight that the spatial-spectral contrastive framework is a contribution. In my opinion, it is not the first work using spectral-based GNN and spatial-based GNN as two different views for GCL.\n\n2. Because of the sparsity, eigenvalues usually obtain by randomized SVD. The computational cost is nk^2 rather than n^2k usually. I guess you do not use SVD designed for dense matrices. If you do you can check randomized SVD that may help you.\n\n3. The novelty of eigenMLP: the eigenMLP looks like SignNet + position embedding. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your positive comments!\n\n> **Q1: I think the eigenMLP is the main contribution but I don't know why the authors try to highlight that the spatial-spectral contrastive framework is a contribution.**\n\nA1: We agree that the main contribution of our paper is the design of EigenMLP, which is an effective and efficient spectral encoder. On the other hand, most GCL methods focus on a single domain, i.e., spatial or spectral, and fewer methods work on both domains. Therefore, we list the spatial-spectral contrastive framework as our contribution. In the revision, we will discuss the difference between our model and existing two-view GCL methods.\n\n> **Q2: If you do you can check randomized SVD that may help you.**\n\nA2: We express gratitude for your valuable feedback. Subsequent testing proves that random SVD can further reduce the complexity of the preprocessing. Coupled with the fact that our model is efficient during the training phase, the whole process is more scalable and efficient. \n\nSpecifically, we compare the sparse eigenvalue decomposition (EVD) algorithm (numpy.linalg.eigh) and the randomized SVD algorithm (sklearn.utils.extmath.randomized_svd). The outcomes demonstrate a notable acceleration in computation. For instance, in the context of the Pubmed dataset, the EVD procedure takes approximately **70 seconds**, while the SVD process is accomplished in nearly **2 seconds**.\n\n> **Q3: The novelty of eigenMLP: the eigenMLP looks like SignNet + position embedding.**\n\nA3: Generally, both SignNet and EigenMLP can be seen as positional encoding methods. The novelty of EigenMLP comes from two perspectives:\n\n1. SignNet can only address the sign-ambiguity problem, while its advanced version, BasisNet, comes with a heavy computational burden. In contrast, EigenMLP presents an efficient and effective approach that simultaneously tackles the sign- and basis-ambiguity issues. As demonstrated in Table 10, EigenMLP is 30 times faster than BasisNet.\n\n2. EigenMLP provides an efficient way to perturb the graph spectrum for better contrastive learning. Existing spectral augmentation methods, e.g., SpCo [1] and SPAN [2], need to decompose and reconstruct the graph structure, which is inefficient. EigenMLP can directly learn new eigenvalues from the Fourier features of raw eigenvalues. However, as we can see from Table 1, both SignNet and BasisNet cannot utilize the eigenvalues.\n\n> **Q4: What is the T in Eq.8?**\n\nA4: The symbol $T$ is the period of the Fourier features, which is a hyper-parameter in our model.\n\n> **EigenMLP is able to outperform other spectral-based GNNs with the usual semi-supervised setting?**\n\nA5: We conduct the semi-supervised experiment in the Pubmed dataset because it has the standard semi-supervised data split, i.e., 20 nodes per class for training and 1000 randomly sampled nodes for test [1]. We choose three competitive spectral GNNs as baselines: GPR-GNN [2], ChebyNet [3], and BernNet [4]. Notably, EigenMLP does not use feature information, while spectral GNNs use graph spectrum to filter the node features. Therefore, to perform a fair comparison, we use two different settings:\n\n1. **Pubmed w/ features**: In this setting, we concate the representations learned by EigenMLP and original node features, and feed them into an MLP for classification. Spectral GNNs remain unchanged.\n\n2. **Pubmed w/o features**: In this setting, we replace the node feature matrix with an identity matrix, and feed it into spectral GNNs for classification. As for EigenMLP, we only use the eigenvectors and eigenvalues.\n\nThe results are shown as follows, from which we can see that EigenMLP has a great improvement over spectral GNNs in learning positional information. Remarkably, even with the inclusion of node features, EigenMLP still maintains its superiority over the baselines.\n\n| | Pubmed w/ features |Pubmed w/o features |\n:-: | :-: | :-:\n| EigenMLP | **80.15±0.43** | **75.62±0.16** |\n| GPR-GNN | 79.92±0.38 | 71.42±0.12 |\n| ChebyNet | 78.53±0.26 | 52.44±0.38 |\n| BernNet | 79.86±0.24 |61.76±0.45 |\n\n[1] Semi-Supervised Classification with Graph Convolutional Networks. ICLR 2017.\n\n[2] Adaptive Universal Generalized PageRank Graph Neural Network. ICLR 2021.\n\n[3] Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering. NeruIPS 2016.\n\n[4] BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximation. NeurIPS 2021.\n\n> **Q6: Why the MLP is so close to EIgenMLP in Table 5?**\n\nA6: In Table 5, Pubmed and Facebook are transductive datasets, while Molbace is non-transductive. In transductive datasets, the training, validation, and test nodes share the same adjacency matrix. Consequently, the signs and coordinates of eigenvectors remain consistent during the training and inference stages. Therefore, the model performance will not be influenced by sign- and basis-ambiguity. As a result, the performance of MLP is close to that of EigenMLP in Pubmed and Facebook. On the contrary, EigenMLP outperforms MLP a lot in the Molbace dataset.\n\nThe same phenomenon can also be observed in the stability experiment (Section 6.5). When the training and test data employ the same perturbation, the performance of MLP is comparable to that of EigenMLP, as evident from the results in the diagonal entries of Tables 7 and 8. However, in cases where different perturbations are applied, EigenMLP consistently outperforms MLP, as indicated by the results in the off-diagonal entries.\n\n"}, {"review_id": "QT9bHRqdvj", "reviewer": "Reviewer_QJUG", "summary": "The authors present a novel approach called Sp2GCL that combines spatial and spectral views of graphs using EigenMLP, an informative and stable spectral encoder. The proposed method shows promising results in learning effective graph representations and outperforms other spectral-based methods in terms of both performance and efficiency.", "questions": "- How are the scalar eigenvalues extended to high-dimensional Fourier features in EigenMLP?\n- What are the overheads of training and inference in EigenMLP?\n- How does EigenMLP handle the sign and basis ambiguity issues in spectral features?\n", "limitations": "N/A", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "This work proposes contrasting two views in the spectral domain and spatial domain and introduces a novel encoder called EnigenMLP to encode spectral domain information, which has not been done by former work.", "weaknesses": "- The contribution of the article is considered limited as the traditional Graph Neural Network (like GCN), which can be understood as spectral filtering in the spectral domain, is similar to the EnigenMLP proposed in this work. \n\n- Simply contrasting these two representations might not lead to significant improvements, as indicated in the results where there is no clear enhancement and suspicion of cherry-picking.\n\n- The article suggests that the proposed method may not offer significant improvement over Graph Convolutional Network methods, and the results indicate a lack of noticeable enhancement. This raises concerns about the effectiveness of the proposed approach.\nThe article mentions that the contribution of the work is relatively limited, indicating that the proposed method may not introduce significant advancements beyond existing approaches.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your helpful suggestions!\n\n> **Q1: The contribution of the article is considered limited as the traditional Graph Neural Network (like GCN), which can be understood as spectral filtering in the spectral domain, is similar to the EnigenMLP proposed in this work.**\n\nA1: EigenMLP is fundamentally different from the spectral filtering applied in Graph Neural Networks (GNNs) for several reasons:\n\n1. EigenMLP serves as a method for encoding the **positional information** of nodes. In contrast, spectral filtering of GNNs utilizes graph spectrum to filter the noise present in **node features**.\n\n2. The expressive power of traditional GNNs is limited by the  Weisfeiler-Lehman test [1]. In contrast, incorporating the positional information can surpass this limitation [2]. Therefore, the expressive power of EigenMLP is better than message-passing GNNs.\n\n[1] How powerful are graph neural networks? ICLR 2019.\n\n[2] Graph neural networks with learnable structural and positional representations. ICLR 2022.\n\n> **Q2: Simply contrasting these two representations might not lead to significant improvements, as indicated in the results where there is no clear enhancement and suspicion of cherry-picking.**\n\nA2: We make an additional experiment to validate the effectiveness of the spatial-spectral contrast. Specifically, we directly concatenate the spatial features $A^{2}X$ and the spectral features $U\\rho(\\Lambda)$ as non-contrastive representations, i.e., $[A^{2}X, U\\rho(\\Lambda)]$. Then we use a  linear classifier, which is the same as Sp2GCL, to evaluate the performance of non-contrastive representations. The experiment is conducted in the Pubmed and Flickr datasets. Results are shown below, from which we can see that the spatial-spectral contrast contributes a lot to learning graph representations.\n\n| | Contrastive | Non-contrastive |\n:-: | :-: | :-:\n| Pubmed | 82.3±0.3 | 80.1±0.2 |\n| Flickr | 52.05±0.33 | 50.27±0.47 |\n\n> **Q3: The article suggests that the proposed method may not offer significant improvement over Graph Convolutional Network methods, and the results indicate a lack of noticeable enhancement. This raises concerns about the effectiveness of the proposed approach. The article mentions that the contribution of the work is relatively limited, indicating that the proposed method may not introduce significant advancements beyond existing approaches.**\n\nA3: We need to clarify that graph convolutional networks (GCNs) are **semi-supervised methods**, implying that they need label supervision to update the model parameters. In contrast, our model is an **unsupervised method** that does not require the usage of labels. Simply comparing the performance of GCNs and our method is unfair. Moreover, we can see that in some datasets, our model outperforms GCNs a lot. For example, in the Pubmed dataset, our method (accuracy=82.3) has an improvement of 4% over GCNs (accuracy=79.0), which demonstrates the effectiveness of the proposed method.\n\nAdditionally, we do not mention that the contribution of our work is relatively limited. We consistently highlight that our model is an effective and efficient method.\n- In terms of effectiveness, our model achieves comparable performance over various graph-related tasks.\n- In terms of efficiency, Sp2GCL is 10 times faster than the state-of-the-art spectral-based GCL method, and EigenMLP is 30 times faster than existing sign- and basis-invariant spectral encoders.\n\n> **Q4: How are the scalar eigenvalues extended to high-dimensional Fourier features in EigenMLP?**\n\nA4: *We describe the Fourier features of eigenvalues in Equation 5.*\n\nSpecifically, we stack the sin and cos values of the scalar eigenvalues with different periods to construct its high-dimensional Fourier features, i.e., $[\\sin(\\lambda), \\cos(\\lambda), \\sin(2\\lambda), \\cos(2\\lambda), \\cdots \\sin(T\\lambda), \\cos(T\\lambda)]$.\n\n> **Q5: What are the overheads of training and inference in EigenMLP?**\n\nA5: *The time overheads of EigenMLP and Sp2GCL are shown in Tables 9 and 10.*\n\nHere we briefly report the results for a quick reference. In summary, Sp2GCL is 10 times faster than the state-of-the-art spectral-based GCL method, e.g., SPAN, and EigenMLP is 30 times faster than existing sign- and basis-invariant spectral encoders.\n\n| Table 9 | Pre-processing | Training (100 epochs) | Inference ($\\times 10^{-3}$) |\n:-: | :-: | :-: | :-: \n| SpCo | 127.16 | 22.81 | 4.5 |\n| SPAN | 658.62 | 142.92 | - |\n| Sp2GCL | 66.44 | 17.79 | 6.2 |\n\n| Table 10 | Facebook (k = 100) | moltox21 (7831 Graphs) |\n:-: | :-: | :-:\n| MLP | 2.24 | 2.09 |\n| SAN | 127.23 | 60.58 |\n| BasisNet | 169.83 | 84.64 |\n| EigenMLP | 5.34 | 3.14 |\n\n> **Q6: How does EigenMLP handle the sign and basis ambiguity issues in spectral features?**\n\nA6: *We describe how EigenMLP solves the sign and basis ambiguities in Section 4.2. We also theoretically prove this in Theorem 1, Section 5.1.*\n\n- For sign-ambiguity, EigenMLP simultaneously takes the positive and negative eigenvectors as input, thus learning sign-invariant representations.\n- For basis-ambiguity, EigenMLP leverages the learned eigenvalues to weight eigenvectors, thus eliminating the influence of coordinate rotation.\n\n\n"}, {"review_id": "YAwQQyc748", "reviewer": "Reviewer_ieZM", "summary": "The paper proposes a method for Graph Contrastive Learning (GCL) by contrasting the spatial and spectral views ($Sp^2GCL$). The spatial view is obtained using a message passing GNN. For the spectral view the authors propose an equivariant model called EigenMLP. EigenMLP precomputes the k smallest eigenvalues and corresponding eigenvectors for a graph. The eigenvectors are made sign invariant using positive and negative eigenvectors as in SignNet. Permutation/Basis equivariance is obtained by learning MLP weights from fourier features of the eigenvalues. The method uses the same node/graph representations as positive views and from different graph/nodes as negative views. The InfoNCE contrastive function is used as the objective. After the self supervised training, a linear classifier is used on the downstream task of node/graph classification/prediction.", "questions": "1. Regarding the views for a node/graph, the spectral views are obtained from the eigendecomposition that are made equivariant to sign and basis and the spatial views are obtained from an MPNN. This would give a fixed view for every node/graph and the concern is for a node/graph how to obtain multiple positive views? In the absence of multiple views the learning may be limited to fixed representations and may not scale well for larger models.\n2. As pointed out by the authors, the spatial method learns local features and the spectral method learns global properties. Is it always the right approach to contrast them in the proposed manner? In which cases would it work and how do practitioners make a decision?\n", "limitations": "Some of the limitations have been addressed in the paper. Please refer to the Weakness and Questions section to address further limitations.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1) Paper proposes an important direction of combining spatial and spectral views\n2) The method obtains competitive results compared with baselines\n", "weaknesses": "Regarding the views for a node/graph, the spectral views are obtained from the eigendecomposition that are made equivariant to sign and basis and the spatial views are obtained from an MPNN. This would give a fixed view for every node/graph and the concern is for a node/graph how to obtain multiple positive views? In the absence of multiple views the learning may be limited to fixed representations and may not scale well for larger models.\n\n**Minor Typos:**\n1. The eigenvalues and eigenvectors **encoder** the global shapes [13] and node absolute positions $\\rightarrow$ The eigenvalues and eigenvectors **encode** the global shapes [13] and node absolute positions\n2. It can **encoder** both the information of eigenvalues and eigenvectors $\\rightarrow$ It can **encode** both the information of eigenvalues and eigenvectors\n3. In practice, the sign-invariant neural networks may slow down model **converge** $\\rightarrow$ In practice, the sign-invariant neural networks may slow down model **convergence**\n4. Therefore, EigenMLP can learn more stable representations **again** structural perturbations $\\rightarrow$ Therefore, EigenMLP can learn more stable representations **against** structural perturbations\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your positive comments!\n\n> **Q1: How to obtain multiple positive views? In the absence of multiple views the learning may be limited to fixed representations and may not scale well for larger models.**\n\nA1: Constructing multiple positive views is important for contrastive learning. To achieve this goal, the most widespread approach is to augment the input data.\n\nSeveral approaches exist for augmenting spatial features [1][2], including randomly dropping edges, nodes, and features. On the other hand, for spectral features, we can create multiple positive views by selecting different numbers of eigenvectors. For example, in descending order of eigenvalues, we can select the first $k$, $2k$, ..., eigenvectors. Each of these views captures distinct frequencies of node positions, thereby enabling the construction of multi-scale representations.\n\n[1] Graph Contrastive Learning with Augmentations. NeurIPS 2020.\n\n[2] Graph Contrastive Learning Automated. ICML 2021.\n\n> **Q2: Minor Typos**\n\nA2: Thank you for carefully checking our paper. We will polish our paper based on your suggestions in the revision.\n\n> **Q3: Is it always the right approach to contrast them in the proposed manner? In which cases would it work and how do practitioners make a decision?**\n\nA3: The definition of positive and negative views, as well as the selection of contrastive objective function, continue to be open challenges in the field of contrastive learning. Consequently, spatial-spectral contrast may not always be the right approach, depending on the property of the data. \n\nIntuitively, the spatial methods encode the local feature information through message-passing and the spectral methods learn the positional information. Therefore, spatial-spectral contrast works well **if the positional information can complement the feature information**. However, it may not yield favorable results if the feature information dominates the classification accuracy. For example, in some heterophilic datasets, where two connected nodes tend to have different labels, the performance of MLP is better than GNNs [3]. In such cases, the positional information may not complement the feature information.\n\n[3] Graph Neural Networks for Graphs with Heterophily: A Survey\n\n"}]

Author rebuttal:
We extend our gratitude to all the reviewers for their valuable feedback and insightful suggestions. We have diligently addressed the majority of the questions and suggestions raised during the official review process, and have provided comprehensive responses to individual reviewers in the corresponding rebuttals.

We are delighted to be recognized for our efforts in this research. We would like to express our appreciation to Reviewer 9zn6 for acknowledging the novelty and significance of our model in the context of spectral-based methods. Our thanks also go to Reviewer xYrm for endorsing our motivation and theoretical contributions. We thank Reviewer QJUG for the helpful suggestions. Lastly, we would like to convey our gratitude to Reviewer ieZM for their strong acknowledgment of the novelty and effectiveness of our work.

Meta-review: The paper introduces a new spectral encoder for graphs, and apply it to contrastrive learning to achieve demonstrably competitive accuracy at a fraction of the computational cost if compared with other spectral methods. The paper received overall positive reviews, highlighting the relevance of the problem, the novelty of the proposed spectral encoder, and the idea of combining spatial and spectral views in one method. Some concerns on the adversarial robustness and missing comparisons with semi-supervised methods were adequately addressed in the rebuttal with additional quantitative results, together with a deeper theoretical discussion. The paper is a solid contribution in the graph learning area, and is a step forward in bridging spatial and spectral graph learning methods.
Decision: Accept (poster)