Spectral Augmentation for Self-Supervised Learning on Graphs
Authors: Lu Lin
Jinghui Chen
Hongning Wang
Venue: ICLR 2023 notable top 25% (2023)
Keywords: graph self-supervised learning
graph spectral theory
graph augmentation

Abstract: Graph contrastive learning (GCL), as an emerging self-supervised learning technique on graphs, aims to learn representations via instance discrimination. Its performance heavily relies on graph augmentation to reflect invariant patterns that are robust to small perturbations; yet it still remains unclear about what graph invariance GCL should capture. Recent studies mainly perform topology augmentations in a uniformly random manner in the spatial domain, ignoring its influence on the intrinsic structural properties embedded in the spectral domain. In this work, we aim to find a principled way for topology augmentations by exploring the invariance of graphs from the spectral perspective. We develop spectral augmentation which guides topology augmentations by maximizing the spectral change. Extensive experiments on both graph and node classification tasks demonstrate the effectiveness of our method in self-supervised representation learning. The proposed method also brings promising generalization capability in transfer learning, and is equipped with intriguing robustness property under adversarial attacks. Our study sheds light on a general principle for graph topology augmentation.

Published as a conference paper at ICLR 2023
SPECTRAL AUGMENTATION FOR SELF-SUPERVISED LEARNING ON GRAPHS
Lu Lin L Jinghui Chen', Hongning Wang The Pennsylvania State University, Uniiversity of Virginia (lulin, jzc5917) @psu. edu, hw.5xvirrinnia.. edu
ABSTRACT
Graph contrastive learning (GCL), as an emerging self-supervised learning tech- nique on graphs, aims to learn representations via instance discrimination. Its performance heavily relies on graph augmentation reflect invariant patterns that are robust to small perturbations; yet it still remains unclear about what graph invariance GCL should capture. Recent studies mainly perform topology augmen- tations in uniformly random manner in the spatial domain, ignoring its influence on the intrinsic structural properties embedded in the spectral domain. In this work, we aim to find principled way for topology augmentations by exploring the invariance of graphs from the spectral perspective. We develop spectral augmen- tation which guides topology augmentations by maximizing the spectral change. Extensive experiments on both graph and node classification tasks demonstrate the effectiveness of our method in unsupervised learning, well as the generalization capability in transfer learning and the robustness property under adversarial attacks. Our study sheds light on a general principle for graph topology augmentation.
INTRODUCTION
Graph neural networks (GNNs) Kipf & Welling 2017 Veličković et al. 2018 Xu al. 2019 have
advanced graph representation learning in (semi-)suuerrs Jsupervised manner, yet it requires supervised labels and may fail to generalize (Rong et al. 2020). To obtain more generalizable and transferable representations, the self-suuer learning (SSL) paradigm emerges which enables GNNs to learn from pretext tasks constructed on unlabeled graph data (Hu et al. 2020c by You et al.] 2020b Din al.) 2020a). As state-of-the-art SSL technique, graph contrastive learning (GLL) has attracted the most attention due to its remarkable empirical performance /Velickovic et al. 2019 Zhu et al. 2020
Hassani & Khasahmadi 2020 You et al. 2021 Suresh al. | et al. 2021).
typical GCL method works by creating augmented views of the input graph and learning rep- resentations by contrasting related graph objects against unrelated ones. Different contrastive ob-
jects are studied on graphs, such as node-node (Zhu et al., 2020 [021 |eng et al., 2020), node- (sub)graph (Veličkovié et al. 2019 Hassani & Khasahmadi 22200] Sun al.) 2019)) and graph- graph (Biclak et al.) 2222 Thakoor et al.
et al. (021)) contrastive pairs. The goal of GCL capture graph invariance by maximizing the congruence between node or graph representa- tions in augmented views. This makes graph augmentation one of the most critical designs in GCL, as it determines the effectiveness of the contrastive objective. However, despite that various GCL methods have been proposed, it remains mystery about what graph invariance GCL should capture.
Unlike images, which can augmented naturally highlight the main subject from the background, it is less obvious to design the most effective graph augmentation due to the complicated topology structure of diverse nature in different graphs (e.g., citation networks (Sen al.) 20088. social networks (Morris et al. 2020), chemical and biomedical molecules (Li et al. 2021 Hu al. (020b)), as discussed in the survey (Ding et al.) 2022). We argue that an ideal GCL encoder should preserve structural invariance, and an effective augmentation focuses perturbing edges leading to large changes in structural properties; and by maximizing the congruence across the resulting views, information about sensitive friable structures will be minimized in the learned representations.
Most existing works perform topology augmentations a uniformly random manner (Zhu et al., 2020 Thakoor al. 2021), which achieves certain level of empirical success, but is far from optimal:

---

Published as a conference paper at ICLR 2023
recent studies show that perturbations on different edges post unequal influence the structural properties (Entezari et al. 2020; Chang et al. (021a) while the uniformly random edge perturbation ignores such differences. Such discrepancy suggests an opportunity to improve the common uniform augmentation by considering structural properties to better capture structural invariance. Since graph spectrum summarizes many important structural properties (Chung & Graham 1997). propose to preserve spectral invariance as proxy of structural invariance, which refers to the invariance of the encoder's output to perturbations on edges that cause large changes on the graph spectrum.
To realize the spectral invariance, we focus on designing a principled augmentation method from the perspective of graph spectrum, termed SPectral AugmentatioN (SPAN). Specifically, we search for topology augmentations that achieve the largest disturbance on graph spectrum. By identifying sensitive edges whose perturbation leads to a large spectral difference, SPAN allows the GNN encoder to focus on robust spectrtal components (which can be hardly affected by small edge perturbations) and to reduce its dependency on instable ones (which can be easily affected by the perturbation). Therefore, the learned encoder captures the minimally information about the graph (Tishby et al. 2000 Tian et al. 2020) for downstream tasks.
We provide an instantiation of GCL on top of the proposed augmentation method SPAN, which can also be easily paired with different GCL paradigms as only requires a one-time pre-computation of the edge perturbation probability. The effectiveness of SPAN is extensively evaluated various benchmark datasets, which cover commonly seen graph learning tasks such as node classification, graph classification and regression. The applicability of SPAN is tested under various settings including unsupervised learning, transfer learning and adversarial learning setting. In general, SPAN achieves remarkable performance gains compared the state-of-the-art baselines. Our study can potentially open up new ways for topology augmentation from the perspective of graph spectrum.
2 RELATED WORKS
Graph Contrastive Learning (GCL) leverages the InfoMax principle (Hjelm et al. 2018 to maximize the correspondence between related objects on the graph such that invariant property across objects is captured. Depending on how the positive objects are defined, one line of work treats different parts of a graph as positive pairs, while constructing negative examples from a corrupted
graph (Hu al. 2020b: Jiao et al. 2020 Veličković al. 2019 Peng al. 2020 Sun et al. (019))
In such works, contrastive pairs are defined as nodes (Veličkovic et al. 2019) or substructures (Sun
al., 2019) v.s. the entire graph, and the input graph v.s. reconstructed graph (Peng et al. 2020).
The other line of works exploit graph augmentation to generate multiple views, which enable more
flexible contrastive pairs (Thakoor et al. 2021 Bielak al. 2021 Suresh et al. 2021 You et al. 2021
Feng et al. 2022 Ding et al. (022). By generating augmented views, the GNN model is encouraged to encode crucial graph information invariant to different views. In this work, we focus on topology augmentation. As parallel effort in self-supervise learning, augmentation-free techniques (Lee) cet al. 2022, Wang et al., 2022) avoid augmentation but require special treatments (e.g., kNN search or clustering) to obtain positive and negative pairs, which is out scope of this work.
Graph Topology Augmentation. The most widely adopted topology augmentation is the edge perturbation following uniform distribution (Zhu et al. 2020; Thakoor et al.) 2021 Bielak et al. 2021 You et al. 2020a). The underlying assumption is that each edge is equally important to the property of the input graph. However, recent study shows that edge perturbations do not post equal influence to the graph spectrum (Chang et al. 2021a) which summarizes a graph's structural property. To better preserve graph property that has been ignored by uniform perturbations, domain knowledge from network science is leveraged by considering the importance of edges measured via node centrality (Zhu et al.) 2021). the global diffusion matrix (Hassani & Khasahmadi] (0020). and the random-walk based context graph (Qiu et al. (020). While these works consider ad ad-hoc heuristies, our method targets at the graph spectrum, which comprehensively summarizes global graph properties and plays a crucial role in the spectral filter of GNNs. To capture minimally sufficient information from the graph and remove redundancy that could compromise downstream performance, adversarial training strategy is paired with GCL for graph augmentation Suresh et al. (2021): You et al. (2021): ); Feng et al. (2022). following the information bottleneck (IB) (Tishby et al. 20000 and InfoMin principle (Tian et al. 2020). While the adversarial augmentation method requires frequent back propaaatonn during training, our method realizes a similar principle with a simpler but effective augmentation by maximizing the spectral difference of views with only one-time pre-computation.
2

---

Published as a conference paper at ICLR 2023
3 PRELIMINARIES
Notations, We focus on connected undirected graphs G = (X, A) with n nodes and m edges, where X e R describes node features, and A E R denotes its adjacency matrix such that Aij = 1 if an edge exists between node and j. otherwise Aij O. The unnormalized Laplacian matrix of the graph is defined as Ln D- A, where D = diag A ,,) is the diagonal degree matrix with entry DH E==1 Aty and 1, being an all-one vector with dimension n. The normalized Laplacian matrix further defined as n Lap( A) I, D-112-1/00 AD- -1/2, where I, is n. identity matrix.
Graph Spectrum. Graph representation learning can be viewed as graph signal processing (GSP). The graph shift operator (GSO) in GSP commonly adopts the normalized Laplacian matrix Looen and admits eigendecomposition diag(A1...... )z) consists of the real cigenvalues which are known as graph spectrum, and the corresponding U = [1 u,]] IR=*" collecting the orthonormal eigenvectors are the spectral bases. Graph spectrum plays a significant role in analyzing and modeling graphs, as discussed in Appendix A On one hand, it comprehensively summarizes important graph structural properties, including connectivity (Chung & Graham 1997), clusterability (Lee et al., 2014)) and etc. On the other hand, as the essence of GNNs, spectral filter is defined on the graph spectrum to manipulate graph signals in various ways, such as smoothing and denoising (Schaub & Segarra 2018).
Lmorm UAU The diagonal matrix A eig(nn
Graph Representation Learning. Given graph G E G, the goal of node representation learning is to train an encoder fo : G + _ such that fG) produces a low-dimensional vector for each node in G' which can be served in downstream tasks, such as node classification. One can further obtain a graph representation by pooling the set of node representations via a readout function Is : R - Rd such that go (Jo(G) outputs a low-dimensional vector for graph G which can be used in graph-level tasks. We use θ to denote all the model parameters.
Graph Contrastive Learning by Topology Augmentation. GCL methods generally apply graph augmentation to perturb the input graph and decrease the amount of information inherited from the original graph; then they leverage the InfoMax principle (Hjelm et al. 2018) over the perturbed graph views such that an encoder is trained capture the remaining information. Given a graph G' E 9 with adjacency matrix A, we denote a topology augmentation scheme as TAA and sampled augmented view as ((A) T(A). GCL with two-branch augmentation can be formulated as follows:
GCL: min (t (A), (A), θ), s.t. (A) ~ i,),, E {1,2}
where the contrastive loss LaCI. measures the disagreement between representations from contrastive positive pairs. The topology augmentation scheme determines a distribution from which perturbed graphs are sampled in augmented views, and its detailed formulation will be presented in Section 5
4 STRUCTURAL INVARIANCE MATTERS IN GCL
Structural Invariance. Despite that multiple topology augmentation methods have been proposed, little effort is made to answer a fundamental question: what invariance information should GCL capture? We argue that an ideal GCL encoder should preserve structural invariance, which is defined as the invariance of the encoder's output when perturbing a constrained number of edges that cause large changes to the structural properties of the input graph:
LOCL(A, t(A), θ) S a, s.t. t(A) = argmax AA ((A))
p(t(A))p(((A)))
(2)
where D).))) is distance metric, and p(-) can be defined vector-valued function of the graph's structural properties, such as the diameter of the graph, whether the graph is connectivity, the clustering coefficient, etc. One may focus on partieular properties when designing the function p(-)- To realize structural invariance via GCL, effective augmentation should focus on sensitive edges whose perturbation can easily cause large property change. Then by minimizing the contrastive loss LOCL, the edges causing structural instability are regarded as noise, and the information related to these edges will be ignored by the encoder, inspired by the InfoMin principle (Tian et al. 2020).
Capturing structural invariance requires the topology augmentation to identify the sensitivity of edges to the structural properties, while the augmentation with uniformly random edge perturbation fails to realize this. The discrepancy motivates the following pre-analysis to demonstrate a potential opportunity of improvement upon uniform perturbation.
3

---

Published as a conference paper at ICLR 2023
68
30
Pre-analysis. We apply GRACE (Zhu et al. 2020) the Cora dataset, and compare the original uniformly random augmentation in GRACE with simple heuristic based the clustering property of nodes. We take the clustering property as example demonstrate our insight, as it is an intuitive manifestation among many structural prop- erties. To be more specific, we compare two topology augmentation heuristics: 1) uniform augmentation that removes edges uniformly random; 2) clustered augmen- tation that flips edges between different node clusters with a larger probability, which can cause large changes to the clustering property of the graph suggested by recent studies (Chiplunkar et al. 2018 Lin et al. (021). We use the original graph in one augmentation branch, and compare GCL performance under the uniform or the clustered augmentation in the other branch. More experiment details are provided in Appendix C.I The downstream node classification performance evaluated by F/ score is compared in Figure la We can clearly observe that under the same perturbation budget indicated by the x-axis, the cluster-based strategy achieves better performance on the downstream task. The performance gap between these two simple strategies suggests distinct opportunity to improve over the uniformly random augmentation by considering structural invariance.
86-
Unifrom Clustered
Spectral ShantrallCaange Change
25
Uniform
Clustered
60-
12
10
76
0.75 Perturbation Rate
Perturbation
(a) Performance
(b) Spectral difference
Figure I: Comparison between uniform
and clustered augmentations.
From Structural Invariance Spectral Invariance. Directly capturing structural invariance for GCL is nontrivial, as it requires simultancous characterization of multiple structural properties. Fortunately, recent studies show that graph spectrum comprehensive summary of many graph structural properties (Chung & Graham 1997: Lee et al., 2014), including clustering, connectivity and etc. For example, the change on clustering property (by perturbing inter-cluster edges) can be reflected on the graph spectrum: 1) empirically, Figure Tb compares the spectral change (measured by the L2 distance of graph spectrum between the original and the augmented graph), and we can observe larger spectral change for the slusterbbased augmentation; 2) theoretically, we can also prove that the edge flips between different clusters causing larger clustering change result in larger spectral change, as discussed in Appendix [D.6] Therefore, we use graph spectrum ladder to capture structural properties, and propose spectral invariance as a proxy of structural invariance.
Spectral invariance requires the encoder's output stay similar when perturbing edges that cause large changes to the graph spectrum. Formally, it is defined as:
CACL(A, t(A), 9) S s.t. t(A)= argmax A-
P P(cig(Lap(AA)) cig(Lap(t(A)))) (3)
where the distance between two graph structures is measured on the graph spectrum. An effective topology augmentation should pay more attention to sensitive edges that introduce large disturbances the graph spectrum, whose influence should then be eliminated by contrastive learning. Unlike the proof-of-concept cluster-based heuristic, we aim on designing principled augmentation by directly maximizing the spectral change.
5 SPECTRAL AUGMENTATION ON GRAPHS
In this section, we introduce SPectral AugmentatioN (SPAN) on graph topology to preserve spectral invaraince in GCL. We first define the edge perturbation based topology augmentation scheme determined by Bernoulli probability matrix. Based on that, formulate our augmentation principle as a spectral change maximization problem.
Edge Perturbation Based Augmentation Scheme. We focus on topology augmentation using edge perturbation. Following the GCL formulation in Eq. [ we define topology augmentation T(A) as Bernoulli distribution B(Ar)) for each entry A.j. All Bernoulli parameters constitute
probability matrix A E [0, 1|nxx. _ We can sample an edge perturbation matrix E E {0. 1 1 where Eij ~ B(Di)) indicates whether to flip the edge between node i and j. and the edge is flipped if E,; = otherwise remaining unchanged. A sampled augmented graph is then obtained via:
((A) = A + Co E, C À A-A
(4)
where A is the complement matrix of the adjacency matrix A. calculated by A - I, A. with 1, I,) denoting the fully-connected graph without self-loops. Therefore. C A A e (-1, 1) j denotes legitimate edge adding or removing operations for each node pair: edge adding
4

---

Published as a conference paper at ICLR 2023
between node i and is allowed if Ciy 1, and edge removing is allowed if Ci 1. Taking the Hadamard product C E finally gives valid edge perturbations to the graph.
Since E is matrix of random variables following Bernoulli distributions, the expectation of sampled augmented graphs in Eq. 4 is E|](A)] A + C o A. Therefore, the design of A determines the topology augmentation scheme. Taking uniformly random edge removal as example, the entry Ai is set as a fixed dropout ratio if Cjj = 1; and O otherwise. While we focus on edge perturbation, an extension of the proposed principle node dropping augmentation is discussed in Appendix [
Spectral Change Maximization. Motivated by our observation in Section 4 instead of setting fixed values for A in uniform perturbation, we propose optimize it guided by graph spectrum. Specifically, we aim to search for A that in expectation maximizes the spectral difference between the original graph and the augmented graph. Note that while the perturbations are sampled from A via the resulting Bernoulli distributions, A on all edges is jointly optimized. Denoting the normalized Laplacian matrix of A as Lap(A), the graph spectrum can be calculated by A eig(Lap(A)), We formulate the following problem search for the desired A in a single augmentation branch:
Single-way scheme SpANsingte:
max |eig(Lap((A Co A)) eig(Lap(A))) AES
(5)
where S = (sis E [o, 1 1|== ||s|]| S <e} and e controls the perturbation strength. By solving Eq. 5 we obtain the optimal Bernoulli probability matrix A', from which augmented views are sampled that in expectation differ the most from the original graph in graph spectrum. Eq. [3 provides one augmented view; to further introduce flexibility for two-branch augmentation framework and enlarge the spectral difference between the resulting two views, we extend Eq. 5 as follows:
Double-way way SPAN
max A.A.ES
|eig(Lap(A + C A1) - eig(Lap(A + Co A2)) (6)
where A; is the Bernoulli probability matrix for augmentation branch i's scheme (A) in Eq.
Note that 5 is special case of Eq. 6 when setting 2₂ = 0. Eq. 6 gives better flexibility yet also makes the optimization problem harder solve; thus based triangle inequality, we maximize its lower bound instead: max ,. ASES [|eig(Lap(A (A + C A 1))ll
+ +C Co A2))
Therefore, A I and A can be independently optimized towards opposite directions: maximizing the spectral norm in one branch, while minimizing it in the other, which leads to the final objective:
Opposite-directio dirrction scheme SPANopposiee
max Las (A1), and min A
(A)
AIES
where Cas( (A) = ||iig(Lpp(A A + Co A)) measures the Graph Spectral norm under augmentation scheme with A. For scheme Ti (A), Ai produces views that overall have larger spectral norm than the original graph, while for T2)A), A2 produces views with smaller spectrum. We can understand them as setting a spectral boundary for the input graph such that the encoder is trained to capture information that is essential and robust regarding perturbations within this region.
Optimizing A and Ag. Eq. 7 can be solved via projected gradient descent (for A2) ascent (for A1). Taking A₂ as an example, its update works as follows:
1 (1) = Ps (t-1)
v Los (t-1))
(
where Nh > 0 is the learning rate for step t, and Ps(a) = argmin ||s - all2 is the projection operator at a over the constraint set S. The gradient V A ((-1) can be calculated via chain rule, with closed-form gradient over cigenvalues: for a real and symmetric matrix L. the derivatives of its k-th eigenvalue d / u (Rogers 1970). where u, the corresponding eigenvector. Note that the derivative calculation requires distinct eigenvalues, which does not hold for graphs satisfying automorphism (Godsill 1981). To avoid such cases, we add a small noise term to the adjacency matrix] e.g., A + Co A + (N N NT2 where each entry in N is sampled from a uniform distribution 24 1) and e is very small constant. Such a noise addition will almost surely break the graph automorphism, thus enabling valid gradient calculation of eigenvalues. The convergence of optimizing opposite A and A₂ is empirically shown in Appendix D.7 Mcanwhile, the behavior of spectral augmentation in the spatial domain is analyzed in Appendix D.6
Scalability. For T' iterations, the time complexity of optimizing such a scheme is (TT)²) due to the eigen-decompossitin eig(-) in Las, which is prohibitively expensive for large graphs. To
'The form of (N + N )/2 keep the perturbed adjacency matrix symmetric for undirected graphs
5

---

Published as a conference paper at ICLR 2023
Augmentation Scherne
Graph View
Node-level Representation
Graph Representation
max (ss(A)
Readout Function g
Encoder
Input Graph
RAJAD: ((A))
M(A) TAIAD
H
Shared
Shered Readaut Function
GoL
A
Augmentation Schame
Graph View
GNN Encoder
Node-level Representation
Graph-lavel Representation
min L (4((A)
T(A TAA :
(())~ T(AIAA)
H
Z(2)
Figure 2: A GCL instantiation using SPAN. The augmentation scheme pre-computed, and the augmented views are sampled from the scheme. The contrastive objective is to maximize the cross- level mutual information between node and graph representations.
reduce the computational cost, instead of conducting eigen- degeopoecooooiiioonn on the full graph spectrum. we appeal selective decooppccooioiioonnn Algorithm (Parlett & Scott 1979). We consider both low and high eigenvalues in estimating the spectral change, because they play important roles in graph analysis and GNN design, discussed in Appendix A. More detailed analysis of eigenvalues and the performance when varying K on real-world graphs are provided in Appendix D.2, Th time complexity is reduced O n and the empirical running time for pre-computing the augmentation scheme is provided in Appendix D. We can further improve the scalability using practical treatments for large graphs (Qiu et al. 2020) (e.g., ego-nets sampling, batch training), which is left as our future work.
K lowest- and highest-eigenvalues via the Lanczos
DEPLOYING SPAN IN GCL
We provide an instantiation of GCL with the proposed spectral augmentation, termed GCL-SPAN, as illustrated in Figure 2 Its detailed description can be found in Appendix B Note that our focus is on the augmentation, and this GCL instantiation using widely-adopted designs is purposely to showcase how easily one can plug SPAN in most GCL frameworks.
The augmentation scheme can be first set up by pre- pre-computing the probability matrices A₁ and A₂ based on Eq. 7 For each iteration of contrastive learning, we sample two augmented graphs for the input graph: 4 (A) ~ TT(AAA))))) and 1/ (2( T(A The augmented graphs then fed into GNN encoder fe. which outputs two sets of node representations H (2)
(() E R readout pooling function 96 is applied to aggregate and transform the node representations and obtain graph
representations (1)), z22) RRd Following (Velickovic al., 2019 Hassani & Khasahmadi, 2020). given training graphs G, we adopt the contrastive objective LGCL that maximizes the cross-level correspondence between local node and global graph representations, which is to preserve local similarities and global invariants:
GCL-TAGS: min LoCL (t 0.6
Σ GEg
=
((H (2) + T( z
20))
9
n
1=1
s.t. 4:4 (A) ~ T(A (1,2), = argmax Las (), A, argmin AES Las (A)
(9)
where 1 (2)) calculates the mutual information between variables X, and X2, and it can be lower bounded by InfoNCE (Van den Oord et al.) 2018 Poole al., 2019). Specifically, denoting
cosine similarity as cos(;,)) ), we estimate the mutual information as follows:
1( (b) log exp(cos (a) (b)
(10)
Ej=1 exp(cos H ((1))
where and b index the augmented views, and H is the node representations for negative examples in the batch. Note that the optimization of augmentation scheme is a one-time pre-computation thus does not introduce any extra complexity the contrastive learning process. The proposed augmentation can be paired with other advanced choices in the contrastive paradigm, such as dynamic dictionary and moving averrge encoder (He al. 2020 Qiu et al. 2020) to fit different application scenarios. Since only require to precompute A and A₂ once, the time complexity totally acceptable.

---

Published as a conference paper at ICLR 2023
Table 1: Node classification performance in unsupervised setting. The metric is accuracy (%). The best and second best results are highlighted with bold and underline respectively.
Dataset
PubMed
Wiki-CS
Amazonn Computer
Phouoo
Couutbor-
Raw S-GCN
48.93.10.00
50.00
68.33.10000
71.08.10.00
73.81:10.00
78.53:10.00
90.37 0.00
81.3440.35
70.42::::45
79.82::0.41
17.19:40.12
86.51
92.42:10. 16
93.03
R-GCN
56.44:0.224
63.52:+0.25
73.92+0.32
12.95=b0.58
82.46:::0388
90.08::0.48
90.64:0.29
GRACE
83.3340043
12.10:20.54
78.72+:0.13
80,14:+0.48
89.53:1:.35
92.78=00.30
91.12=0.200
BGRL
83.63.10.38
72.52.10.40
79.83.10.25
79.98.10.13
0.119
93.17.10.30
93.31 1.0.3
Baselines
GBT
80.24:0.42
69.39:100.56
78.29++0.43
76.65-+0.62
08.14:10.33
92.63-20.44
92.95=0.117
MVGRL
85.16.10.52
12.14:1:1335
80.13:10.84
17.52.10.08
87.52:10.11
91.74:10.00
92.11 1:0.12
83.67.10.44
71.48:10.26
78.87:10:49
78.35-10.05
88.94.10.155
92.53-10.16
93.10:10.01
GMI
83.0210.333
72.45:00.12
79.94110.25
74.85
82.21::0.31
90.68:10.17
91.08 0:056
DGI
02.34 71.85.10.74
76.82.10.61
75.35.10.14
83.95.10.47
91.61 1.0.22
92. 92.15:10..6
GCI-SPAN
85.86
72.76:10.63
81.54:0.24
82.13--0.15
90.09:+0.32
93.52:1:0.6
93.91
7 EXPERIMENTS
We perform evaluations for node classification, graph classification and regres- sion tasks under unsupervised learning, transfer learning and adversarial attack settings. Following prior works (Zhu et al.) 2021;; Thakoor et al. 2021, Veličković al. 2019), we use GCN (for node prediction tasks) and GIN (for graph prediction tasks) as the base encoder fo for all methods to demonstrate the performance gain from contrastive learning. We adopt the following evaluation protocol for downstream tasks (Suresh et al. 202T): based on the representations given by the encoder, train and evaluate a Logistic classifier a Ridge regressor. We repeat experiments for 10 times and report the mean and standard derivation of the evaluation metrics. The experimental details about datasets, baselines and configurations can be found in Appendix C
Experiment Setup:
7.1 UNSUPERVISED LEARNING
To evaluate the quality learned representations, linear model is trained for the downstream tasks using these learned representations as features and the resulting prediction performance is reported. The effectiveness of SPAN is evaluated on both node- and graph-level prediction tasks.
Node Classification Task. We first evaluate the effectiveness of SPAN node classification datasets ranging from citation networks to co-purchase networks. We compare against GCL methods that augment topology with uniformly random edge perturbation (e.g.. GRACE (Zhu al. 2020),
BGRL (Thakoor et al. 202T), GBT (Bielak et al.] 202T)), centrality (GCA (Zhu et al. 2021)). diffusion matrix (MVGRL (Hassani & Khasahmadij 2020)) and the original graph (e.g., GMI (Peng et al., 2020) and DGI (Veličković et al.) 2019)). As a reference, we also consider fully semi- supervised GCN (S-GCN), randomly initialized untrained GCN (R-GCN) and using the raw node features as node representations (Raw-X). All the methods exploit a 2-layer GCN as backbone and a downstream linear classifier with the same hyper-paramene feature masking in SPAN, following the setup in SOTA works (Zhu et al. 2021 Bielak et al. 2021).
for a fair comparison. We adopt random
Table compares the instantiation GCL-SPAN with baselines. Comparing GCL-SPAN with MVGRL and GCA which augment graphs via domain knowledge (e.g., node centrality or graph diffusion), the performance gain suggests the advantage of the spectral augmentation over previous domain- knowledge based heuristics. Meanwhile, SPAN is shown to be more effective than the uniformly random augmentation adopted in GRACE, BGRL and GBT. To demonstrate the direct gain of SPAN, also compare the performance of directly plugging our proposed augmentation into several existing frameworks in Appendix D.3) and to compare the effectiveness different augmentation schemes, compare the performance when using different augmentation schemes for GCL instantiation in Appendix D.5 These experiments show promising improvement by our proposed SPAN.
We test on multiple graph classification and regression datasets ranging from social networks, chemical molecules to biological networks. We compare SPAN with five GCL methods including InfoGraph (Sun et al. 2019), GraphCL You et al. 2020a),, MVGRL (Hassani & Khasahmadi] 2020), AD-GCL (with fixed regularization weight) (Suresh et al. 2021) and JOAO (v2) YYou et al. 202I). We use a 5-layer GIN encoder for all methods, including a semi cemi-supervised S- GIN and randomly initialized R- R-GIN. A readout function with a graph pooling layer and a 2-
Graph Prediction Task.
7

---

Published as a conference paper at ICLR 2023
Table 2: Graph representation learning performance in unsupervised setting. TOP shows the biochem- ical and social network classification results on TU datasets (measured by accuracy%).. BOTTOM shows the regression (measured by RMSE) and classification (measured by ROC-AUC%) results on OGB datasets. The best and second best results are highlighted with bold and underline respectively.
Riochemical Molecules
Social Networks
Dataset
NCI1
PROTEINS
MUTAG
DD
COLLAB
RDT-B
RDT
IMDB
IMDB M
S-GIN
22.39:42.76 62.98=0.10
78.27=
90.41:4.11 74.8743..6
74.82:40.92
86.79
53,2843.17
7188
28.46:12.31
R-GIN
69.05-:0.33
07.61
74.22+00.30
63.08+0.10
58,97200113
27.52+00.1
51.86++0.33
32.81
InfoGraph
68.13:+0.59
72.57=00.65
8..71=1.777
75.23:00.39
00.35=:0.64
78.79:22.14
51,11
71.11:0888
48.66:20.67
Duselmnes
GraphC1L
68.54:10.55
72.86:11.01
88.29:1:.11
74.70:10.70
71.26:10.55
82.63-10.99
53.05:1..40
70.80:10.77
48.49:00633
MVGRL
68.68=00:42
74.02+00.32
89.24+1.31
75,20=00.55
73.10=00.56
81,20+00.69
51,87=0.65
71884+0,78
50.4+00.2
AD-GCL
69.67:10.51
73.5910.66
89,25::145
74,49:00.52
73.32:#0.11
85.52:10,79
53.00+:0.2
71.57:1.001
49.04
JOAO
72:99::0.75
71.25+00.5
15.20=
66.9111.75
70.40+2.21
18.35
45.57=2.86
71.60+0.86
51.14+0.69
GCL-SPAN 71.43+0044 75.78:10.41 89.12 75.78:100.5 75.01::0.45
83.62+00.44
54.10::0.49 7.665::0.69 52.16:10.72
Regression (Metric: RMSF)
Classification (Metrie: ROC-AUC%)
Dataset
molesol
mollipo
molfreesoly
molbace
molbhbbg
malclintex
mallox21
molsider
S-GIN
1173:40.057
0.757:0.018
2.755::0.349
72.97+t
68.174 488
88.1442..51
74.91-10.51
57.60 1.40
R-GIN
1,706=0.180
1.075=0.022
7.526+:2.119
75.07=22.23
64.48+2.46
72.29+4.15
71.53=0.74
62.29
InfoGraph
1.344:10.188
1.005=000033
10.005:24.89
74.74::3.6
66.33-2..79
64.50-15.32
69.74:1..7
60,54400.00
Baselines
GraphCCL
1.27240.009
0.910=0.016
7.679::2.748
74.32:42.70
68,22+1899
74.92+4442
12.40+11001
61.76#1.11
MVGRI.
1.433-10.145 0.962:10.036
9.02411.982
74.20:12.31
1.32
73.84144225
70.48:10.3
61,9410.94
AD-GCL
1.217:10.07
0.842:00.08
5.150:::0:24
76,37-22.03
68,24+
80.77+3.92
71.42:0.73
63 19:9..99
JOAO
1.285:10.21
0.865100.032
5.131:10.722
74.48.11994
67.62.11.29
78.21114.12
71.8310.92
62.7310.92
GCL-SPAN
1218::00052
0.802:10.019
4.5311100463
76.74:22.02
69.59:11.34
80.28::2:42
72.83-10.22
64.87:10.88
MLP is applied to generate graph representations. We adopt the given data split for OGB dataset, and use 10-fold cross validation for TU dataset it does not provide such a split.
Table 2 summarizes the graph prediction performance. GCL-SPAN gives the best results on 13 out of 77 datasets, of which 10 are significantly better than others. Compared with GraphCL and JOAO which select the best combination of augmentations for each dataset from a pool of methods including edge perturbation, node dropping and subgraph sampling, GCL-SPAN using only edge perturbation based augmentation still outperforms them. This suggests the effectiveness of graph spectrum in guiding topology augmentation. Compared with MVGRL, our performance gain mainly comes from the augmentation scheme, as these two methods share similar contrastive objectives, and our augmentation guided by graph spectrum is clearly more effective than the widely adopted uniformly random augmentation. While AD-GCI. and GCL-SPAN follow a similar principle to remove edges that carry con-impottant and redundant information, GCL-SPAN is more ficxible since the augmentation scheme is optimized in an independent pre-computation step without interfering with the contrastive learning procedure.
7.2 TRANSFER LEARNING
This experiment evaluates the generalizability of the GNN encoder, which is pre-trained on source dataset and re-purposed on a target dataset. Table 3 reports the performance on chemical and
Table 3: Graph classification performance in transfer learning setting on molecular classification task. The metric is ROC-AUC% The best and second best results are shown in bold and underline.
Pre-Train
ZINC-2M
PP1-306K
Dataset
Fine-Tune
BBBP
Tox21
SIDER
ClinTox
BACE
HIV
MUV
ToxCast
No-Pte-Train-GIN
65.81445
74.0=0.8
57.3#116
58.0+444
70.1155
75.3+1.9
718822.5 63.44:0.6
64.8:11. 1.0
InfoGraph
68.81.888
75.3::0.5
58.4.088
69.9-33.0
75.9-:1.6
76.0-0077
75.3125
62.7-0.4
6.5
Baselines
GraphCi.
69.710077
73
60.5
76.0.12.7
154.14
7.2
698
62.411066
67.910.9
MVGRL
69.0::0.5
74.5-0.6
62.21006
77.8:122
77.21:0
77.120.
7.33 62.61.05
68.7
AD-GCL
70.0+:1.1
76,5=088
63.3+088
79.8:13.5
7855+088
78.3=10
72.3+16
63.1+0.7
68.8+13
JOAD
7144:0.9
74.320.6
60.5:10.7
81.0116
75.5.1.3
77.5112
73.7210
63,24:0.5
64.0216
GCL-SPAN
70.0.10.7
18.0 64.7
80.7.12.1 79.910.77
77.8.0066
73.8:0.99
64.2.10.4 7..0.1088
8

---

Published as a conference paper at ICLR 2023
Table 4: Node classification performance on Cora in adversarial attack setting (measured by aceu- racy%) The best and second best results are highlighted with bold and underline respectively.
Atlack
Random
DICE
Attack
Mettack
Clean
Ratio
0.05
0.2
0.2
0.05
0.2
0.05
0.2
S-OCN
81.34:0.335
81.11:0032
80.02:1:0.36
79.42:10.37
78.37::0.42
00.12:
79.43:0..32
50.29:00411
31.04::0.48
GRACE
83,33.10433
83.23.10.88
82.57.10.48
81.28.10.39
80.72.10.44
82.59.1.335
80.23.10.38
67.42.10.99
55.26.10.53
BGRI
83.63::0.38
03.12:::.34
83.02:10.39
08.83:
81.92:1:.33
02.10::0.37
80.9811022
08.23::0448
60.42::0.44
Baxelines
GBT
80,24+00.2
80.53:+0.30 39
80.20:+0.35
80.32:+0.32
80.20:+:034
79.89=0041
78.25+0.49
63.26::0.09
53.89+0..55
MVGRL
85.16:2:0.52
65.28:10.49
84.211:0.42
03.78::0.35
K3.02::0:44
03.79:10.39
82.46:10.52
73.43:+0.55
61.49:10..6
83.67.10:44
63.33.10.46
82.49.10.37
82.20.10.32
81.82.10.45
81.8310.336
79.89.1047
58.2510.68
49.25
GMI
83,02-40033 83.14=00388
82.12-+0.44
82,42=00444
81.13+:0,49
82.13=00.39
80,26::0.48
60,59+00.54
53.67+00.68
DGI
82.34:10..4
82.10.10.58
81.03:10.52
80.48:10.38
79.89:10.43
01.30.10.54
79.88.10.58
71.42.10.63
63.93:10.58
GCI-SPAN
85.86:10.57 86.29:10.52
86.21
85.52.10.59
84.30-10.63
85.08.10.77
84.28.10.82
77.28 09.92.1...3
biological graph classification datasets from (Hu et al. 2020b). Appendix C.S studies an even more challenging setting (Qiu et al. 2020) where the encoder is pre-trained on social networks and transferred multiple oft-of-domain tasks. A reference model without pre-training GIN) is compared to demonstrate the gain of pre-training. GCL-SPAN is shown to be more effective in learning generalizable encoders, which supports our augmentation principle: by perturbing edges that cause large spectral changes, the encoder is pre-trained to ignore unreliable structural information, such that the relationship between such information and downstream labels can be removed to mitigate the overfitting issue. The generalizability of the GNN encoder molecule classification depends on the structural fingerprints such as subgraphs (Duvenaud et al. 2013). JOAO and GraphCL using subgraph sampling augmentation is outperformed by GCL-SPAN, which suggests that the graph spectrum could be another important fingerprint to study chemical and biological molecules.
Poo-Pre-Train
7.3 ADVERSARIAL ROBUSTNESS
This setting demonstrates the robustness of GCL when the input graph is adversarially poisoned. The augmentation scheme is optimized and the representations are learned from graphs poisoned by different structural attack strategies, including Random (which randomly edges), DICE (Waniek) jet al., 2018) (which deletes edges internally and connects nodes externally across classes), GF- Atlack (Chang et al., 2020) (which maximizes low-rank matrix approximation loss) and Met- tack (Zügner& & Günnemann 2019) (which maximizes the training loss via meta- meta-gradiintss. We test the perturbation ratios {0.05, 0.2}: x edges are flipped for graph with m edges.
Table reports the node classification performance under the adversarial attacks. The encoders leamned by GCL methods with graph augmentations are generally more robust to perturbed graphs compared with S-GCN. GCL-SPAN outperforms baselines with a clear margin, which demonstrates good property of SPAN: even though it is not explicitly designed for adversarial robustness, the encoder can stay invariant to the adversarially perturbed graph if its spectrum falls into the range captured by the ipposite-direction augmentation scheme. Compared with the parallel efforts in designing robust GNNs (Entezari et al. 2020 Zhu et al. 22099) Jin et al. (020b)) we provide new insight using graph spectrum as tool study graph invariance under perturbations.
8 CONCLUSION
In this work, we proposed a principled spectral augmentation scheme which generates topology augmentations by perturbing graph spectrum. Our principle is that a well-behaving GNN encoder should preserve spectral invariance to sensitive structures that could cause large changes on graph spectrum. To achieve this goal, we search for the augmentation scheme that would mostly change the graph spectrum of the input graph, which further leads to an aoposite-direction augmentation scheme that changes the graph spectrum towards opposite directions in two views. The proposed augmentation can be paired with various GCL frameworks, and the extensive experiments demonstrate the performance gain by the proposed augmentation method, Currently we only focus on topology augmentation, and ignore its interplay with node features, which is another important dimension in GCL. Recent studies show the relationship between graph homoohily/hhterophily and GNNs, which suggests future effort to explore the alignment between graph topology and node features in GCL.

---

Published as a conference paper at ICLR 2023
9 ACKNOWLEDGEMENTS
This work is supported by the National Science Foundation under grant 2007492, 11S-1838615 and IIS-1718216.
REFERENCES
Piotr Bielak, Tomasz Kajdanowicz, and Nitesh Chawla. Graph barlow twins: self-supervised representation learning framework for graphs. arXiv preprint arXiv:2106.02466, 2021.
Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen. Beyond low-frequency information in graph con- volutional networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 3950-3957, 2021.
Aleksandar Bojchevski and Stephan Günnemann. Adversarial attacks on node embeddings via graph poisoning. In International Conference Machine Learning, pp. 695-704. PMLR, 2019.
Heng Chang, Yu Rong, Tingyang Xu, Wenbing Huang. Honglei Zhang, Peng Cui, Wenwu Zhu, and Junzhou Huang. A restricted black-box adversarial framework towards attacking graph embedding models. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 3389-3396, 2020.
Heng Chang, Yu Rong, Tingyang Xu, Yatao Bian, Shiji Zhou, Xin Wang, Junzhou Huang, and Wenwu Zhu. Not all low-pass filters are robust in graph convolutional networks. Advances in Neural Information Processing Systems, 34, 2021a.
Heng Chang, Yu Rong, Tingyang Xu, Wenbing Huang, Somayeh Sojoudi, Junzhou Huang, and Wenwu Zhu. Spectral graph attention network with fast eigen-approximation. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pp. 2905-2909, 2021b.
Ashish Chiplunkar, Michael Kapralov, Sanjeev Khanna, Aida Mousavifar, and Yuval Peres. Testing graph clusterability: Algorithms and lower bounds. In 2018 IEEE 59th Annual Symposium Foundations of Computer Science (FOCS), pp. 497-508. IEEE, 2018.
Fan RK Chung and Fan Chung Graham. Spectral graph theory. Number 92, American Mathematical Soc., 1997.
Asim Kumar Debnath, Rosa L. Lopez de Compadre, Gargi Debnath, Alan J Shusterman, and Corwin Hansch. Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity. Journal of medicinal chemistry, 34 (2):786-797, 1991.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in neural information processing systems, 2016.
Kaize Ding, Zhe Xu, Hanghang Tong, and Huan Liu. Data augmentation for deep graph learning: A survey. ACM SIGKDD Explorations Newsletter, 24(2):61-77, 2022.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan Adams. Convolutional networks on graphs for learning molecular fingerprints. Advances in neural information processing systems, 28, 2015.
Negin Entezari, Saba A Al-Sayouri, Amirali Darvishzadeh, and Evangelos E Papalexakis. All you need is low (rank) defending against adversarial attacks on graphs. In Proceedings of the 13th International Conference Web Search and Data Mining, pp. 169-177, 2020.
Shengyu Feng, Baoyu Jing, Yada Zhu, and Hanghang Tong. Adversarial graph contrastive learning with information regularization. arXiv preprint arXiv:2202.0649)) 2022.
Chris D Godsil. On the full automorphism group of graph. Combinatorica, 1(3):243-256, 1981.
10

---

Published as a conference paper at ICLR 2023
Rafael Cómez-Bombarelle Jennifer N Wei, David Duvenaud, José Miguel Hernández-Lobato, Benjamín Sánchez- Sánchez-Lengehne Lengeling, Dennis Sheberla, Jorge Aguilera-Iparraauinnn Iparraguirre Timothy D Hirzel, Ryan P Adams, and Alán Aspuru-Guzik, Automatic chemical design using data-driven continuuus representation of molecules. ACS central science, 4(2):268-21) 276, 2018.
Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Guo, Mohammad Gheshlaghi Azar, et al. Bootstrap your own latent-a new approach to seff-supervised learning. Advances Neural Information Processing Systems, 33:21271 1-21284, 2020.
David Hammond, Pierre Vandergheynst, and Rémi Gribonval. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 30(2):129-1500 2011.
David K. Hammond, Yaniv Gur, and Chris R. Johnson. Graph diffusion distance: A difference
measure for weighted graphs based on the graph laplacian exponential kernel. In 2013 IEEE Global Conference on Signal and Information Processing, pp. 419-422, 2013. doi: 10.1109/
GlobalSIP:201.6673699
Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi- representation learning graphs. In International Conference on Machine Learning, pp. 41 1664626. PMLR, 2020.
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 9729-9738. 2020.
R Devon Hjelm, Alex Fedorov, Samuel Lavoie- Marchildon, Karan Grewal, Phil Bachman, Adam Trischler, and Yoshua Bengio. Learning deep representations by mutual information estimation and maximization. arXiv preprint Xrviv: /8..ivi:...... 1808.06670, 2018
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. Advances in neural information processing systems, 33:22118 12-1333,, 2020a.
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. In International Conference Learning Representations, 2020b. URL
Ziniu Hu, Yuxiao Dong, Kuansan Wang, Kai-Wei Chang, and Yizhou Sun. Gpt-gnn: Generative pre-training of graph neural networks. In Proceedings of the 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2020c.
Yizhu Jiao, Yun Xiong, Jiawei Zhang, Yao Zhang, Tianqi Zhang, and Yangyong Zhu. Sub-graph contrast for scalable self-supervised graph representation learning. 2020 IEEE International Conference Data Mining (ICDM), pp. 122-231. IEEE, 2020.
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, 2020a.
Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang. Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 66-74, 2020b.
Nabil Kahale. Eigenvalues and expansion of regular graphs. J. ACM, 4265)10091-1106 sep 1995. ISSN 0004-5411. doi: 10.1145/21011..200136 URL.https::/bbi../////000 210118. 210116
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017.
James R Lee. Shayan Oveis Gharan, and Luca Trevisan. Multiway spectral partitioning and higher- order cheeger inequalities. Journal of the ACM (JACM), 6106),133, 2014.
11

---

Published as a conference paper at ICLR 2023
Namkyeong Lee, Junseok Lee, and Chanyoung Park. Augmentation free self superviee learning on graphs. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 7372-7380, 2022.
Michelle M. Li, Kexin Huang, and Marinka Zitnik. Representation learning for networks in biology and medicine: Advancements, challenges, and opportunities. CoRR, abs/2104.04883 2021.
Lu Lin, Ethan Blaser, and Hongning Wang. Graph structural attack by spectral distance, 2021. URL https://arxiie org/ als 2111. 00684
Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao-Way Chang, and Doina Precup. Is heterophily a real nightmare for graph neural networks to do node classification? arXiv preprint Ne:::1009055444 2021.
Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. Parameterized explainer for graph neural network. Advances in neural information processing systems, 33:19620- 11119960-1996 19600,1991111111 2020.
Péter Mernyei and Cätälina Cangea. Wiki-cs: A wikipedia-based benchmark for graph neural networks. arxiv preprint arXiv:2007.02901, 2020.
Benjamin A Miller, Michelle Beard, and Nadya T Bliss. Matched filtering for subgraph detection in dynamic networks. In 2011 IEEE Statistical Signal Processing Workshop (SSP), pp. 509-512. IEEE, 2011.
Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. In ICML 2020 Workshop on Graph Representation Learning and Beyond (GRL+ 2020), 2020.
Andrew Ng, Michael Jordan, and Yair Weiss, On spectral clustering: Analysis and an algorithm.
Advances in neural information processing systems, 14, 2001.
Beresford N Parlett and David $ Scott. The lanezos algorithm with selective orthogonalization. Mathematics of computation, 33(145):217-23,, 1979.
Zhen Peng, Wenbing Huang, Minnan Luo, Qinghua Zheng, Yu Rong, Tingyang Xu, and Junzhou Huang. Graph representation learning via graphical mutual information maximization. In Proceed- ings of The Web Conference 2020, pp. 259-270, 2020.
Ben Poole, Sherjil Ozair, Aaron Van Den Oord, Alex Alemi, and George Tucker. On variational bounds of mutual information. In International Conference on Machine Learning, pp. 5171-5180.
PMLR, 2019.
Jiezhong Qiu, Qibin Chen, Yuxiao Dong, Jing Zhang, Hongxia Yang. Ming Ding, Kuansan Wang. and Jie Tang. Gec: Graph contrastive coding for graph neural network pre- pre-training. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp- 1150-1160,, 2020.
Leonardo FR Ribeiro, Pedro HP Saverese, and Daniel R Figueiredo. struc2vee: Learning node representations from structural identity. In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, pp. 385-394, 2017.
Lynn C Rogers. Derivatives of eigenvalues and eigenvectors. AIAA journal, 8(5):943-944, 1970.
Yu Rong. Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convo- lutional networks on node classification. In International Conference on Learning Representations, 2020.
Michael T Schaub and Santiago Segarra. Flow smoothing and denoising: Graph signal processing in the edge-space. In 2018 IEEE Global Conference Signal and Information Processing (GlobalSIP), pp. 735-739. IEEE, 2018.
Prithviraj Sen, Galilco Namata. Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Roe Radd. Collective classification in network data. Al magazine, 29(3):93-92, 2008
12

---

Published as a conference paper at ICLR 2023
Oleksandr Shehur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arXiv: 181.0868,, 2018.
Fan-Yun Sun, Jordan Hoffmaan, Vikas Verma, and Jian Tang. Infograph: Unsupervised and semi- supervised graph-level representation learning via mutual information maximization. In Interna- tional Conference on Learning Representations, 2019.
Susheel Suresh, Pan Li, Cong Hao, and Jennifer Neville. Adversarial graph augmentation to improve graph contrastive learning. Advances Neural Information Processing Systems, 34, 2021.
Shantanu Thakoor, Corentin Tallec, Mohammad Gheshlaghi Azar, Rémi Munos, Petar Veličković, and Michal Valko. Bootstrapped representation learning graphs. In ICLR 2021 Workshop Geometrical and Topological Representation Learning, 2021.
Yonglong Tian, Chen Sun, Ben Poole, Dilip Krishnan, Cordelia Schmid, and Phillip Isola. What makes for good views for contrastive learning? Advances in Neural Information Processing Systems, 33:6827-6839, 2020.
Naftali Tishby, Fernando C Pereira, and William Bialek. The information bottleneck method. arXiv preprint physics/0004007,, 2000.
Aaron Van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. arXiv e-prints, pp. arXiv-1807, 2018.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. International Conference on Learning Representations, 2018. URL httph:::/tppeeeeeeeeeee
n forum? batammid==rJxxe LdddrrXMMikKa accepted poster.
Petar Veličković, William Fedus, William L.. Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep Graph Infomax. In International Conference on Learning Representations, 2019.
nwt. wow.:orrmmmdd.191.... URL httt:ttts////enreeeet http://nneeeeeee.eeeeerrrrrraaro
Petar Velickovic, William Fedus, William Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. ICLR (Poster), 2(3):4, 2019.
Saurabh Verma and Zhi-Li Li Zhang. Stability and generalization of graph convolutional neural networks In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1539-1548, 2019.
Hoi-To Wai, Santiago Segarra, Asuman E Ozdaglar, Anna Scaglione, and Ali Jadbabaie. Community detection from low-rank excitations of graph filter. In 2018 IEEE international conference on acoustics, speech and signal processing (ICASSP), pp.
IEEE, 2018.
Haonan Wang. Jieyu Zhang, Qi Zhu, and Wei Huang. Augmentation-fiee graph contrastive learning.
arXiv preprint arXiv:2204.04877 2022.
Marcin Waniek, Tomasz P Michalak, Michael J Wooldridge, and Talal Rahwan. Hiding individuals and communities in social network. Nature Human Behaviour, 2(2):139-147, 2018.
Kilian Q Weinberger, Fei Sha, Qihui Zhu, and Lawrence Saul. Graph laplacian regularization for large-scale semidefinite programming. Advances in neural information processing systems, 19, 2006.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019. URL https
//openreview net
Zhitao Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnexplainer: Generating explanations for graph neural networks. Advances neural information processing systems, 32, 2019.
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. Advances in Neural Information Processing Systems, 33: 5812-5823, 2020a.
13

---

Published as a conference paper at ICLR 2023
Yuning You, Tianlong Chen, Zhangyang Wang, and Yang Shen. When does self-supervision help graph convolutional networks? In international conference on machine learning, pp. 10871-10880 PMLR. 2020b.
Yuning You, Tianlong Chen, Yang Shen, and Zhangyang Wang. Graph contrastive learning automated. In International Conference on Machine Learning, pp. 12121-12132. PMLR, 2021.
Jure Zbontar, Li Jing, Ishan Misra, Yann LeCun, and Stéphane Deny. Barlow twins: Self-supervised learning via redundancy reduction. International Conference on Machine Learning, pp. 12310- 12320. PMLR, 2021.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- SAINT: Graph sampling based inductive learning method. In International Conference on Learning Representations, 2020.
Dingyuan Zhu, Ziwei Zhang. Peng Cui, and Wenwu Zhu. Robust graph convolutional networks against adversarial attacks. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery data mining, pp. 1399-1407, 2019.
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep Graph Contrastive Representation Learning. In ICML Workshop Graph Representation Learning and Beyond, 2020. URL /tttp:/axa/ org/abs/ 2006. 04131
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 2021, wwW '21, pp. 2069-2080, New York, NY, USA, 2021. Association for Computing Machinery. ISBN doi: 10.1145/3442381
9781450383127.
URL /ttps///60..033/00..11
3442381. 3449802
Marinka Zitnik and Jure Leskovec. Predicting multicellular function through multi-layer tissue networks. Bioinformatics, 33(14):110--118, 2017.
Daniel Zügner and Stephan Günnemann. Adversarial attacks on graph neural networks via meta learning. In International Conference Learning Reprexentations (ICLR), 2019.
14

---

Published as a conference paper at ICLR 2023
A A REVIEW OF GRAPH SPECTRUM
Graph spectrum plays a significant role in analyzing graph property (e.g., connectivity, cluster structure, diameter etc.) and is the foundation of spectral filters in GNNs. This motivates us guide our proposed topology augmentation method using graph spectrum.
Graph Spectrum and Graph Property. The graph spectrum summarizes important properties related to a graph's global structure, which has been studied in graph spectral theory. We list some widely discussed properties revealed by graph spectrum to support our design: graph spectrum can be used as comprehensive proxy for capturing graph properties in GCL.
Algebraic connectivity (Chung & Graham 1997). also known as Fiedler eigenvalue, of graph is the second-smallest eigenvalue (counting multiple eigenvalues separately) of the Laplacian matrix. This eigenvalue is greater than O if and only if the graph is a connected graph. A corollary is that the number of times 0 appears an eigenvalue the Laplacian is the number of connected components in the graph. The magnitude of this value reflects how well connected the overall graph is.
Diameter of graph can be upper and lower bounded from its spectrum (Chung & Graham 1997) If the graph has distinct cigenvalues, its diameter d is at most r - 1. Meanwhile, if the graph has m edges and n nodes, we can bound the diameter by the first and second smallest non-zero cigenvalues as 1/2m>1 2 d 2 4/nd2. For all k 2 2, we also have d < k log n/ n//z.
Clusterability of graph reveals how easy is to partition the graph, which can be captured by the differences between the smallest successive eigenvalues of connected graphs. The difference between the first two cigenvalues, often referred to as the spectral gap. upper and lower bounds the graph expansion and conductance by the Cheeger inequality (Kahale 1995). Nevertheless, analogous results also hold for higher-order eigenvalues (Lee et al. 2014).
Diffiasion distance (Hammond et al. 2013) between two nodes U, and v/ can be defined as D(u;, vz) = [[) - [L,)], >= (())) - wiii)) where <(L) U*(A)UT and (xxx) decreasing kernel function such ((x) e- Therefore, map that sepa- rates nodes with a specific diffusion distance is obtained when embedding graph nodes using eigenvectors.
Graph Spectrum and GNNs. By viewing GNN models from signal processing perspective, the normalized Laplacian Laven serves as a graph shift operator and defines the frequency domain of a graph. As a result, its eigenvectors U can be considered as the graph Fourier bases, and the eigenvalues A (a.k.a., graph spectrum) correspond to the frequency components. Take one column of node features X as an example of graph signal, which can be compactly represented as x E IR"". The graph Fourier transform of graph signal x is given by & U x and the inverse graph Fourier transform is then x U The graph signals in the Fourier domain are filtered by amplifying or attenuating the frequency components A.
At the essence of GNNs the spectral convolution, which can be defined the multiplication of a signal vector x with a spectral filter I6 in the Fourier domain (Defferrard et al. 2016):
Do (L) * x 100-gg(UAA (UAU xx (A)
(11)
The filter do defines smooth transformation function of the graph spectrum. One can apply spectral filter and graph Fourier transformation to manipulate graph signals in various way, such as smoothing and denoising (Schaub Segarra 2018), abnormally detection (Miller al. (20TT) and clustering (Wai et al. 2018). Here we show how the spectral convlution is defined in two popular GNNS used in our experiments: GCN (Kipf & Welling 2017) and GIN (Xu et al. 2019)
The vanilla GCN (Kipf & Welling 2017) is a first-order approximation of Chebyshev polynomial filter (Hammond et al.) (011)) with go (A) = (2 A)Φ. and the corresponding convolution for d-dimensional signal X 18:
GCN (L) X U(2 XJUXX (L, - x/)
(12)
where & E dxd is the matrix of spectral filter parameters, and renormalization trick I,
1-2 1 1/2 1-1/2 A/ 112 is applied by adding self-loop À A + I GIN (Xu et al.
15

---

Published as a conference paper at ICLR 2023
2019
with equal discriminative power WL test designs spectral convolution
96 (L) * x U(2 + A)U x = (I,, +) + D D- A/DAD 1/2)-112)
(13)
where can be a learnable parameter or fixed scalar. Since the spectral filters go (A) are the key in graph convolutions encode graph signals that are transformed in the Fourier domain. The output of the spectral filters is then transformed back to the spatial domain to generate node representations. Therefore, we aim to augment graphs to influence the graph spectrum and the filtered graph signals, such that the encoder with altered spectral filters is encouraged to stay invariant to such perturbations through GCL.
Some recent literature has shown that graph spectrum is closely related to GNNs' performance. For example, it is proved that the generalization gap of a single layer GCN model trained via T-step
SGD is (x ), where An is the largest eigenvalue of graph Laplacian (Verma & Zhang 2019).
Meanwhile, Weinberger et al. (2006) proved that a generalization estimate is inversely proportional
the second smallest eigenvalue of the graph Laplacian 22. More recent works (Chang al. b021
Luan et al. 2022 Bo et al.) 2021) reveal that both low and high eigenvalues are important for better graph representation learning capture both smoothly varying signals and diversified information.
B ALGORITHM OF DEPLOYING SPAN IN GCL
Algorithm illlsttaates the detailed steps of deploying SPAN in an instantiation of GCL. Note that only one training graph included (e.g., . L. = 1) for node representations learning, and multiple graphs used (e.g.. L 2 2) for graph representation learning.
C EXPERIMENT SETUP DETAILS
This section includes the detailed setup for all experiments, including the procedure of conducting pre-analysis, datasets, baselines, and hyper-parameter settings. The experiments were performed on Nvidia GeForce RTX 2080Ti (12GB) GPU cards for most datasets, and RTX A6000 (48GB) cards for PubMed and Coauthor-CS datasets. Optimizing memory use for large graphs will be our future work.
C. PRE-ANALYSIS EXPERIMENT OF FIGURE
We now introduce the detailed information to reproduce Figure 1 on Cora. This experiment is to show that uniformly random edge perturbation adopted in many GCL methods is not effective enough to capture structural invariant regarding essential graph properties. In contrast to the uniform edge perturbation, we created a cluster based strategy as follows: We first grouped the edges among nodes by whether the end nodes belong to the same cluster (which is given by the spectral clustering algorithm). For inter-cluster edges, we assign a larger removing probability, while for intra-cluster edges we assign smaller removing probability. Note that in expectation, remove the same amount of edges as the uniformly random strategy, but allocate different probabilities to these two groups of edges.
Specifically, an edge removing ratio a indicated by the x-axis of F represents the augmentation strength: for an input graph with m edges, we remove edges to generate augmented graph. For the uniformly random augmentation method (Uniform), each edge is assigned an equal removing probability as σ; for the cluster-based augmentation heuristic (Clustered), given Mimter inter-cluster edges and Mintr = Minter intra-cluster edges, we increase the removing probability of each inter- cluster edge as Finee minn1.20 a m/Mmeer), }. and the removing probability of each intra-cluster edge is decreased to Fintra (ar y Finter minterr) Minm to make sure that in expectation or m edges are removed as in the uniform strategy.
When conducting the contrastive learning procedure, one augmentation branch used the original graph, and the other branch adopted either the uniform or the clustered strategy with a random feature masking with ratio 0.3. For these two GCL methods based on different augmentation strategies, the experiment setup is as follows: both methods used a GCN encoder with the same architecture and hyper-pan paremmtrasssrrs (e.g., 2 convolutional layers with the embedding dimension of 32). Both performed 1000 training iterations to obtain node representations, whose quality was evaluated by using them as features for downstream linear Logistic classifier.
16

---

Published as a conference paper at ICLR 2023
Algorithm 1: Deploying SPAN in an instantiation of GCL
Input :ata (G: = (X,, A,) gl 1... L}; GNN encoder fo; Readout function Ip- Params: : Augmentation optimization step M and learning rate f
Contrastive learning step N and learning rate 3.
Output Trained encoder fe- and readout function før.
/x Lower-level opt cottmization for augmentation scheme in Eq. x/ for each graph 1 + to do Initialize Bernoulli parameters for each graph: (0) 1,1 E [0, 10,1 1,2
E [0, 1j
for / + to MM do
/* Optimize one direction of scheme: maxaes Lea
Las A 1.1 (1--)) ||eig(Lap(A Co A ((11) M) 11 A + Ps Ps|A (t-1) + Vas (--))); )
111
Optimize the other direction of scheme: min Las (A)
+/
Las (A (1-1) [ii + Co A (t-1) >)
>)
1,2
1
(1)
Ps (A
(t-1) VLss
(t- )) based on Eq.
1.2
11
end
A
A
(M) 1,1
A 2
A
(M). 12
13 end
Upper-level optimization for contrastive learning in Eq.
*/
1s Initialize encoder and readout function: g(0), (
16 for t + 1 to N do
Sample batch of graphs (G,,... GG)) 17
18
Sample augmented views for this graph based on Eq. for 1 < to Q do
20
Sample perturbations from Bernoulli distributions: E. ~ B(A,,) E B 1.2):
Calculate topology augmentations: A₁ A + Co E,, A A C E
22
Randomly mask node features to obtain X X1, following Zhu et al. ct al. 2021) if applicable;
2021
Bielak
23
Two graph views are generated as G1,1 = (X,,,, G1, (X1,,, A1,2)
24
end
25
/* Optimize contrastive objective ming, Loor
Define L(Gr,1, G1,,, = Σ' [(H 222) + I(H(") (2) 2())) for Gi;
26
Calculate objective: Lea (0(1-)) ((((-1)) - E L(G1,11 G1,2, 0(1-1) (0l-11);
Update the encoder: g(t) + f(t - (A (1) ()(:-)));
28
Update the readout function: ((t)) +- d(t--1) BV L Lo (0(t-1) ,0((-1)));
end
Output :Encoder fØLNy and readout function hgCN)
17

---

Published as a conference paper at ICLR 2023
Table Node classification dataset. The metric is accuracy.
Data Name
#Nodes
#Edges
#Features
#Classes
Cluster Coefficient
Cora
2,708
5,278
1,433
0.2407
Citescer
3,327
4,552
3,703
6
0.1415
PubMed
19,717
44,324
500
3
0.0602
Wiki-CS
11,701
215,863
300
10
0.4527
Amazon-Coue Conzuu--
13,752
245,861
767
10
0.3441
Amazon-Photos
7,650
119,081
745
8
0.4040
Coauthor-CS
18,333
81,894
6,805
0.3425
Table 6: TU Benchmark Datasets (Morris et al. 2020) for graph classifcation task in unsupervised
leamingg setting. The metric used for classification task is accuracy.
Data Type
Name
#Graphs
Avg. #Nodes
Avg. #Edges
#Classes
NCTI
4,110
29.87
32.30
PROTEINS
1,113
39.06
72.82
Biochemical Molecules
MUTAG
188
17.93
19.79
DD
1,178
284.32
715.66
COLLAB
5,000
74.5
2457.78
REDDIT-BINARY
2,000
429.6
497.75
Social Networks
REDDIT-MULTI-SK
4,999
508.8
594.87
IMDB-BINARY
1,000
19.8
96.53
IMDB-MULTI
1,500
13.0
65.94
Figure Ta reports the mean and standard derivation of Fl score for 10 runs with different random seeds, which measures the downstream task performance. Mcanwhile, we calculated the eigenvalues of the normalized Laplacian matrix of the input graph (A), the augmented graphs with uniform strategy (A (A) and the augmented graphs with clustered strategy (A clusterna)) Figure Ib reports
the L2 distance of eigenvalues between the input and augmented graphs (e.g.. ||A ||A Auussterdl to measure the spectral change.
A uniiform l|2 and
C.2 SUMMARY OF DATASETS
The proposed SPAN is evaluated 25 graph datasets. Specifically, for the node classification task, we included Cora, Citeseer, PubMed citation networks (Sen et al. 2008). Wiki-CS hyper- link network (Mernyei & Cangeal 2020), Amazon-Computer and Amazon-Photo co-purchase net- work (Shchur et al. 2018). and Coauthor-CS network (Shchur et al.) 2018). For the graph classifica- tion and regression tasks, we employed TU biochemical and social networks (Morris al. 2020)). Open Graph Benchmark (OGB) (Hu et al. 2020a) and ZINC (Hu et al. 2220bb] Gömez-Bombarelll al. 2018) chemical molecules, and Protein-Protedd Interaction (PPI) biological networks (Hu et al. 2 & Leskovec 2017). We summarize the statistics of these datasets and briefly introduce the experiment settings on them.
A collection of datasets were used to evaluate node classification performance in both unsupervised learning and adversarial attack settings. and Table summarizes the statisties of these datasets. Cora, Citeseer, PubMed citation networks (Sen et al. 2008) contain nodes representing documents and edges denoting citation links. The task is to predict the research topic of document given its bag-of-worrd representation. Wiki-CS hyperlink network (Mernyei & Cangea 2020) consists of nodes corresponding to Computer Science articles, with edges based on hyperlinks. The task is to predict the branch of the field about the article using its 300-dimension pretrained GloVe word embeddings. Amazon-Coo CrazzonCComuttr, Amazon-Phoo -Phzoo co co-purchase networks (Shchur et al. 2018) have nodes being items and edges representing that two items are frequently bought together. Given item reviews as bag-of of oo-d node features, the task to map items to their respective item category. Coauthor-CS network (Shchur al. 2018) contains node to be authors and edges be co-author
18

---

Published as a conference paper at ICLR 2023
Table 7: OGB chemical molecular datasets (Hu et al. 2020a) for both graph classification and regression tasks in unsupervised learning setting. The evaluation metric used for regression task is RMSE, and for classification is ROC-AUC.
Task Type
Name
#Graph
Avg. #Nodes
Avg. #Edges
#Tasks
ogbg-molesol
1,128
13.3
13.7
Regression
ogbg-molipo
4,200
27.0
29.5
gebg-molfreesoht
642
8.7
8.4
ogbg molbace
1,513
34.1
36.9
oghg-mollee molbbbp
2,039
24.1
26.0
Classification
egbg-molclintor
1,477
26.2
27.9
2
rebg-moltox4/ 7,831
18.6
19.3
12
egbg-molsice
1,427
33.6
35.4
27
Table Biological interaction and chemical molecular datasets (Hu et al. 2020b for graph classifi-
cation task in transfer learning setting. The evaluation metric is ROC-AUC.
Data Type
Stage
Name
#Graph
Avg. #Nodes
Avg. #Degree
Pre-training
PPI-306K
306,925
39.82
729.62
Motein-PProeet Interaction Networks
Fine-tuning
PPI
88,000
49.35
890.77
Pre-training
ZINC-2M
2,000,000
26.62
57.72
BBBP
2,039
24.06
$1.90
Tox21
7,831
18.57
38.58
SIDER
1,427
33.64
70.71
Chemical Molecules
ClinTox
1,477
26.15
55.76
Fine-tuning
BACE
1,513
34.08
73.71
HIV
41.127
25.52
54.93
MUV
93,087
24.23
52.55
ToxCast
8,576
18.78
38.52
relationship. Given keywords of each author's papers, the task is to map authors to their respective field of study. All of these datasets included in the PyG (PyTorch Geometric) library
Two sets of datasets were used evaluate graph prediction tasks under the unsupervised learning setting. TU Datasets (Morris et al. 2020) provides collection of benchmark datasets, and we used several biochemical molecules and social networks for graph classification as summarized in T The data collection is also included in the PyG library following a 10-fold evaluation data split. We used these datasets for evaluation
graph classification task in unsupervised learning setting. Open Graph Benchmark (OGB) (Hu et al. (020a) contains datasets for chemical molecular property classification and regression tasks, which are summarized Table 7 This data collection can be load via the OGB platform and we used its processed format available in PyG
library.
set of biological and chemical datasets were used to evaluate graph classification task under the transfer learning setting, summarized in Table 8 Following the transfer learning pipeline in (Hu et al. 2020b), an encoder was first pre-trained on a large biological Protein- Protein Interaction (PPI) network ZINC chemical molecule dataset, and then was evaluated on small datasets from the same domains.
C.3 SUMMARY OF GCL BASELINES
We compared GCL-SPAN against seven self-supervised learning baselines for node representation learning, including GRACE (hhu et al. 2020), its extension GCA (Zhu et al. 2021), BGRL (Thakoor
19

---

Published as a conference paper at ICLR 2023
et al. 2021 GBT (Bielak et al. 2021), MVGRL (Hassani & Khasahmadi 2020 GMI Peng et al.
2020) and DGI Veličković et al. 2019). Meanwhile, five baselines designed for graph representation
learning were compared, including InfoGraph (Sun et al.) 2019), GraphCL (You et al., 2020a). MVGRI. (Hassani & Khasahmadi| 2020), AD-GCL (with fixed regularization weight) (Suresh et al.,
202T) and JOAO (v2) (You et al. aalla|222) (021). In the contrastive objective design of these methods, different contrastive modes are adopted to compare node-level or graph-level representations. We summarize them based on their contrastive modes as follows:
Node v.s. node mode specifies the contrastive examples as node pairs in local perspective, which focuses on node-level representation learning to serve node prediction tasks. In particular, GRACE (Zhu et al. (2200) employs uniformly random edge removing to generate two views, and treats the same node from two views as positive pairs, and all the other nodes as negatives. GCA (Zhu et al.) 2021) extends GRACE (Zhu al. (2020) with adaptive augmentation consid- ering the node centrality. BGRL (Thakoor et al. (022]) adopts uniformly random edge removing augmentation and applies bootstrapping (Grill al. 2020) framework avoid collapse without negative sampling. GBT (Bielak et al. 2021) uses uniformly random edge removing as graph augmentation and Barlow-twins (Zbontar et al. 2021) objective to avoid collapse without requir- ing negative sampling. GMI (Peng et al. (0200) maximizes a general form of graphical mutual information defined on both features and edges between nodes in input graph and reconstructed output graph.
Graph v.s. node mode takes graph and node pairs as contrastive examples to decide whether they are from the same graph, which obtains both node- and graph-level representations. In particular, MVGRL (Hassani & Khasahmadi 2020) maximizes the mutual information between the local Laplacian matrix and a global diffusion matrix, which obtains both node-level and graph-level representations that can serve for both node and graph prediction tasks. DGI (Veličković et al. 2019) proposes to maximize the mutual information between representations of local nodes and the entire graph, in contrast with a corrupted graph by node shuffling. InfoGraph (Sun et al. 2019) aims maximize the mutual information between the representations of entire graphs and substructures (e.g., nodes, edges and triangles) with different granularity, and it is evaluated on graph-level prediction tasks.
Graph v.s. graph mode treats contrastive examples as graph pairs from global perspective, which mainly targets on graph-level representation learning for graph prediction tasks. Specifically, AD-GCL (Suresh al. 2021) aims avoid capturing redundant information during the training by optimizing adversarial graph augmentation strategies in GCL, and designs trainable non- i..d. edge-dropping graph augmentation. JOAO (You et al., (02T) adopts a bi-level optimization framework to search the optimal strategy among multiple types of augmentations such as uniform edge or node dropping, subgraph sampling. GraphCI. (You et al. (020a) extensively studies graph structure augmentations including random edge removing, node dropping and subgraph sampling.
C.4 HYPER-PARAMETER SETTING
Training Configuration. We summarize the configuration of our GCL framework, including the
GNN encoder and training parameters. For node representation learning, we used GCN (Kipf & Welling 2017) encoder, and set the number of GCN layers to 2, the size of hidden dimension for each layer to 512. The training epoch is 1000. For graph representation learning, we adopted GIN (Xul ct al. 2019) encoder with 5 layers, which was concatenated by a readout function that adds node representations for pooling. The embedding size was set 32 for TU dataset and 300 for OBG dataset. We used 100 training epochs with batch size 32. In all the experiments, we used the Adam optimizer with learning rate 0.001 and weight decay 10-5, For data augmentation, we adopted both edge perturbation and feature masking, whose perturbation ratio a. and o were tuned by grid search among 10.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9) based on the validation set. Note that in our formulation Eq. 9 the augmentation strength Fe where is the number of edges in the input graph.
When evaluating the quality of learned representations downstream tasks in an unsupervised setting, we adopted the evaluation protocol proposed in (Suresh et al. 2021). Specifically, based the representations given by the encoder, trained and evaluated a Logistic classifier or a Ridge regressor with L2 regularization, whose weight was tuned among (0.001, 0.01, 0.1, 1.0, 10.0, 100.0) the validation set for each dataset.
Evaluation Protocol.
20

---

Published as a conference paper at ICLR 2023
C.5 OUT-OF-DOMAIN TRANSFER LEARNING
A more challenging transfer learning setting is proposed in (Qiu et al. 2020), which supports model training on multiple graphs from academic and social networks and transferring to different downstream tasks for other datasets. We further conducted transfer learning experiment under such setting to demonstrate the out-of-domain transferability of our proposed GCL solution GCL.-SPAN. Specifically, pre-train the encoder the Yelp dataset (Zeng et al., (0200) which contains 716.847 nodes and 13.954,8 199 edges; and then the encoder is fine-tuned and evaluated on the US-airport dataset (Ribeiro et al. 2017) for node classification task and three TU social networks (Morris et al., 2020) for graph classification task via 10-fold CV. We sample 80,000 2-hop ego-nets from the Yelp dataset for pre-trale tre-training, and use node degree the node feature for all datasets.
Table 9 summarizes the results of downstream classification accuracy. Overall, we can observe satisfactory performance gain using contrastive learning pre-train the GIN encoder Yelp dataset under such a cross-domain setting. Meanwhile, our proposed method GCL-SPAN outperforms other contrastive learning methods on three out of four downstream datasets.
Table Node and graph classification performance under out-of-domain transfer learning setting. The metric is accuracy%. The best and second best results are highlighted with bold and underline respectively.
Pre-Train
Yelp
Datasel
Node Classification
Graph Classification
Fine-Tune
US-Airport
COLLAB
RDT-B
IMDB-B
No-Pre-Train-Gi
6..42+1.22
74.82::0.92
86.79:22.04
71.83+1933
Baseline
MVGRL
63.83-10.97
74.78++0.84
86.24-+:.26
73.21+1.54
AD-GCL
75.11
88.72:11.53
1..3
JOAO
75.35
87.65:11.72
15.15
GCL-SPAN
65.21 +0.86
7..37++0.73
88.41+1.12
75.89-
D MODEL ANALYSIS
D.1 EMPIRICALLY RUNNING TIME
Recall that the time complexity of augmentation pre-computation is O(TKn²). Table 10 shows empirical running time (in seconds) comparison between the pre-computation of the spectrum- based augmentation scheme and the follow-up contrastive learning iterations. Specifically, in these experiments, we used K = 1000, and T = 50 for node classification on four representative datasets with varying node sizes.
Table 10: Empirical running time (in seconds) on four representative node classification datasets with varying node sizes.
Cora
Amazon-Photo
Wiki-CS
PubMed
#nodes
2, 708
7,650
11, 701
19, 717
Augmentation pre-computation time (K = 1000, /' 50)
105.4
512.6
893.2
2462.3
Contrastive training time (epoch = 1000)
262.9
887.5
1052.4
1429.2
Compared with the time needed for performing contrastive learning, the pre-computation cost is comparable and acceptable. For large-scale graphs with higher time and memory complexity, can further adopt the widely employed treatments in practice (e.g., ego-nets sampling, augmenting sampled ego-nets and training in batch), introduced in GCC QQu al. 2020).
We also want to emphasize that our work is the first step towards effective augmentation for graph contrastive learning by exploiting the graph spectral property. As promising performance gain is
21

---

Published as a conference paper at ICLR 2023
observed in our study, the next step is to improve the efficiency where practical treatments for training in large graphs can be applied.
D.2 INFLUENCE OF CHOOSING EIGENVALUES
Sensitivity of K. reduce the time complexity eigen-decomposition when calculating the spectrum norm LGs(A) (A), we can approximate the norm by only using the K lowest- and highest- eigenvalues. The time complexity of optimizing the augmentation scheme in Eq. / with iterations is OTTKn²). This experiment shows the influence of K to the resulting GCL performance. Since the graphs encountered in the node prediction tasks are much larger than those in graph prediction tasks, used the node classification datasets in Table to conduct this experiment. Specifically, test influence of K on four large graphs representing different types of networks: PubMed citation network, Wiki-CS hyperlink network, Minazon-Computer co-purchase network and Coauthor-CS network. We tuned K among {50, 100, 200, 500, 1000, 5000} for each of the datasets containing 2 10, 000 nodes. The other components of GCL maintained the same, except the resulting augmentation scheme using spectrum norm with different K.
PubMedd
Wiii-S
Amazon Amazon-Computers
Coauthor-Co CS
94-
Accuracy
81
90.0
93
89.5
80
80
89.0
79
79
88.5
91
50
100
200
500
50
100 200
500
1k
100
Figure 3: Node classification performance when choosing K lowest- and highest-eigenvalues
Figure B demonstrates the performance GCL-SPAN on the node classification task when different K was used to generate the augmentation scheme. The x-axis denotes the value of K with "all" indicating that the eigenvalues were used. The performance decreases marginally when we used smaller K, and generally when K = 1000 we can still achieve comparable performance. This suggests that low and high cigenvalues are already quite informative in capturing graph structural properties. Similar phenomenon is also discussed in previous works (Lin et al. 2021): small eigenvalues carry smoothly varying signals (e.g., similar neighbor nodes within the same cluster), while high eigenvalues carry sharply varying signals (e.g., dissimilar nodes from different clusters).
Eipenraluse on WibiES
Elpenvatuees on Amozon Computers
Eigervalues on Cowuthar-CS
160 alc vil (000 (ilo slio
Adc 120
1200
120 300
200 000 100 100 die
Figure 4: Coverage of eigenvalues when choosing K =1k, 5k.
Coverage of K on Graph Spectrum. To show the selection of K still covers moderate range of cigenvalues, we show the distribution of eigenvalues on several real-world graphs in Figure 4 The x-axis denotes the ascending order of n eigenvalues, and y-axis shows the eigenvalue at the corresponding order. Red vertical lines represents K 1000 lowest and highest eigenvalues, while green vertical lines denotes K 5000. We can observe that K 1000 can the eigenvalues, and setting larger K 5000 can well cover most of the eigenvalues. Therefore even if we only choose these eigenvalues, we can already achieve empirically satisfactory performance indicated by Figure 3
moderate range of
D.3 GAIN OF SPAN ON OTHER GCL FRAMEWORKS
In this experiment, we use an ablation study to evaluate the effectiveness the graph spectrum guided topology augmentation scheme when applied different contrastive learning frameworks. We
22

---

Published as a conference paper at ICLR 2023
focus GCL for node-level representation learning, this line of work adopts distinct contrastive objectives (e.g., bootstrapping in BGRL, and Barlow twins in GBT) and contrastive modes (c.g.. node node in GRACE, and node graph in MVGRL), such that can comprchensively demonstrate the effectiveness of our proposed augmentation in covering a variety of GCL frameworks.
Specifically, replace the original uniformly random edge removing augmentation in GRACE, BGRL, GBT, and the diffusion matrix based augmentation in MVGRL with the proposed spectrum based augmentation scheme, and use -SPAN as suffix to denote them. Note that MVGRL-SPAN is basically GCL-SPAN since it uses the same contrastive objective as in MVGRL such that both node- and graph-level representations are obtained serve a broader range of downstream tasks.
Table 11: Node classification performance under unsupervised setting. We plug the spectrum based augmentation to different GCL frameworks, highlighted with suffix -SPAN. The metric is accuracy%. The best results are highlighted with bold.
Dalasel
Cora
Cileseer
PubMed
Wiki-CS
Amazon Computer
Amazon Photo
Cosuthor CS
GRACE
03.33:00.43
72.10::0.54
78.72:0.13
80.14:0..88
89.53-100.35
92.78:10.30
91.12::-0.00
GRACE-SPAN
84.21=0.51
72.87=0.58
79,94=0.22
80.63++0.47
89.95=0041
92.56+:0.38 34
91.98=+0.00
BGRI. 83.63-10338
72.52-10.40
79.83:2..25
79.98:10.13
90.34:10.19
93.17:10.33
93.31-1:.13
BGRL-SPAN
84.34=0.42
72.73:20.44
80.78:20.32
81,04:0.22
90.12:#0.21
93.58:20.39
93,77:10.21
GBT
80.2420.42
69,39:20.5
08.29=0043
76.65:00.62
88,14:20033
92.63-2:0.44
92.95=20.17
GET-SPAN
82.43 0.51
71.12:1..44 0.48
80.05 0.49
78.89 0.54
0.44
92.78.10.43
92.95.10.37
MVGRL.
85. 16.10.0552
72. 1.35
13:10:00.844
77.52-1:008
87.52.10.11
91.74:1:0.00
92.11110.12
MVGRL-SPAN 85.86=0.57
72.76=00.33
81.54=0.24
82.13-:0.15
90.09:10.32
93.52:4.26
93.914:024
Table 11 shows the results of plugging our augmentation scheme on four types of GCL frameworks. We can observe that our augmentation scheme does not depend on a particular contrastive objective, but brings a clear performance gain across different GCL frameworks. Intuitively, our augmentation captures the essential structural properties by perturbing edges that cause large spectral change. Therefore, no matter what contrastive objective or mode is used, maximizing the correspondence of two views encourages the encoder ignore the information carried by such sensitive edges. This demonstrates the importance of studying graph spectral properties for graph augmentation.
D.4 ANALYSIS OF PERTURBATION STRENGHTH
The value of e controls the perturbation strength when generating augmented graphs. larger value indicates that more edges will be dropped/added. Specifically, the optimized scheme A1, Ae constrained by will in expectation perturb e = ae x m edges in the augmented views, where m is the number of edges in the input graph and Øe is the perturbation rate. To analyze the effect of perturbation strength c, we tune oe = c/m = {0.1, 0.2,.... 0.9), and compare the proposed spectral augmentation with uniformly random edge augmentation Figure 2
the same GCL instantiation shown in The performance comparison is conducted under unsupervised node classification task.
PubMed
Wik--5
Amazon-Computerss
Coauthor-CS
85.0
Spectral Aug
85.0
Spectral
Spectral Uniform Aug
Spectral Aug Unitorm Aug
Arcurary
82.5
Unitorm Aug
82.5
Unitorm Aug
90
94
80.0
80.0
92
77.5
77.5
75.0
0.10:20..0.003300 0tt.:400....00.....00880
75.0
0.10.20 3.2.3........000 0.60. 0.10.20.3 0.40.5 0.60.7 U.8..9
Perturbation rate
Perturbation rate
Perturbation rate 6
Perturbation rate &
Figure 5: Node classification performance when tuning perturbation ratio d. e/m.
In Figure the x-axis shows the perturbation rate de, which denotes the perturbation strength normalized by total edge number of the graph (e.g. de = e/m). The performance of spectral augmentation in general is more stable under different perturbation strength, compared with the uniformly random augmentation. This demonstrates that our proposed augmentation can better preserve structural invariance by assigning larger perturbation probability to sensitive edges.
23

---

Published as a conference paper at ICLR 2023
D.5 GAIN OF SPAN COMPARED WITH OTHER AUGMENTATION SCHEMES
We provide additional experiments by fixing the contrastive learning framework, but varying the augmentation schemes, including existing edge perturbation schemes (e.g. the widely used uniformly random edge perturbation, and the diffusion augmentation proposed in MVGRL (Hassani Khasahmadi, 2020)), well as multiple proposed schemes in this paper (e.g., single-way: double- way and opposite-dee -erretiodi schemes). We compare these schemes with our GCL instantiation in Figure on unsupervised node classification tasks.
Table 12:
Node classification performance under unsupervised setting. We plug different augmenta- tion schemes to the GCL instantiation in Figure 2 The metric is accuracy%..
Dataset
Cora
Amazon-Photo
Wiki-CS
PuhMed
Uniformly random
83.87:10.56
91.78=10.27
79.06=10.31
79.02:0..58
Diffusion augmentation
85.16:1..52
91.74 10.07
77.52=00.08
80.13+0.84
Singe-way scheme SPANiingl
84,38+00.42
92.28-0.229
80.76+00.34
80.65+0.31
Double-way scheme SPANa 84.93:10.64
91.81
81.08:0.47
79.43
Opposite-direction scheme SPANoposite
85.86.10.57
93.52:10.26
82.13
81.54.10.24
Table 12 shows the comparison. The opposite-direciie directioo scheme is shown to be the most effective augmentation, especially when comparing with the widely used uniformly random augmentation. The effectiveness the diffusion augmentation depends on the datasets: it is not even as good as the uniformly random method Wiki-CS. The single-way scheme only considers spectrum one branch, thus has limited improvement, and the double-way scheme can not well maximize the spectral difference of two views due to suboptimal solutions to the optimization problem.
D.6 SPATIAL BEHAVIOR SPECTRAL AUGMENTATION SPAN
Case Study on Random Geometric Graph. To intuitively show the spatial change caused by spectral augmentation, we visualize a case study on a random geometric graph in Figure Figure 6a draws the original graph. Figure 6b shows the perturbation probability obtained by maximizing Los A). Figure 6c illustrates the perturbation probability obtained by minimizing Los (A).
(a) Original graph
(b) Edge perturbation probability A by maxa, Las (A1)
(c) Edge perturbation prohability Au by mina, Las LGs(A2)
Figure 6: A case study of the guidedd augmentation scheme on random geometric graph.
We can observe that maximizing the spectral norm assigns larger probability to remove edges bridging clusters such that the clustering effect becomes more obvious, while minimizing the spectral norm tends add edges connecting clusters such that the clustering effect blurred. Intuitively, such an augmentation perturbs these spurious edges that easily affects the structural property (c.g. clustering) to preserve structural invariant, and the information about these edges are disentangled and minimized in the learned representations by contrastive learning.
Theorectical Justification. We also provide a theoretical justification which reveals the interplay of spectral change and spatial change. As derived in Theorem 2 of (Bojchevski & Günnemann, 2019).
given an edge flip Auyy = (1 2A,;) E {-1, 1} between node and j (c.g. if Awyy = 1, adding edge (i, j); otherwise removing edge (i, the k-th eigenvalue is changed X Ax A A
24

---

Published as a conference paper at ICLR 2023
can be approximated by:
À Awy uky Au + uRz))
(14)
where uy is the k-th eigenvector corresponding to the eigenvalue dg. we only focus on the magnitude of eigenvalue change, obtain:
Ad= [ugi uky)² (Ax - I)(uR; 21z)
(15)
Remarks. Since the eigenvectors are normalized, we can treat (u, + u as constant as it is relatively stable value. Based on the theory in spectral clustering (Ng et al. 2001), if the cigenvectors of node and node j have a larger difference (i.e., U. u.,j l large), these two nodes should belong to different clusters. The first term in Eq. T5 suggests larger eigenvalue change, if uąs and Ukj have a larger difference. Therefore, flipping the edge between nodes from different clusters (thus with larger (Mka uky) results in larger spectral change. The second term suggests that such an effect becomes more obvious for eigenvalues close to 0 or 2.
$6.
6620
4015
3.033
830
8279
1222
6.40
6036
1728
(a) Original molecular graph (b) Edge perturbation probability (c) Edge perturbation probability A2 by minA, Les (2)
A by maxa, Les A1)
Figure 7: A case study of the spectrum-guided augmentation scheme MUTAG molecular graphs.
Case Study on MUTAG Molecular Graphs. To further investigate the effect of proposed augmen- tation real-world graphs, we also visualize the augmentation scheme (perturbation probability matrices A1, Az) on several MUTAG molecular graphs in Figure 7 Each row shows one molecular graph with mutagenicity. The first column illustrates the original graph. The second column shows the perturbation probability obtained by maximizing Las A). The last column illustrates the pertur- bation probability obtained by minimizing Los( A). Node color represents the atom type: yellow, blue, red and green denotes carbon, nitrogen, oxygen, and hydrogen, respectively.
can observe that the augmentation scheme assigns high perturbation probability to the edges across different chemical groups. For example, there is higher probability to drop/add edges between NO₂ and carbon rings. By contrastive learning, the information about edges blurring the boundary between NO, and other atoms is minimized. Therefore, the key functional group NO, is preserved, which are shown important for predicting the molecule's mutagenicity (Debnath et al. 1991] Ying
al. 2019 Luo al. 2020
25

---

Published as a conference paper at ICLR 2023
D.7 THE CONVERGENCE OF OPTIMIZING THE SPECTRAL AUGMENTATION
In this section, we show how the graph spectrum norm changes as the augmentation optimization proceeds following Eq. 4 To better show the relative change of graph spectrum compared with the original graph, we calculate Las( A) normalized by the spectrum norm of the original graph, that is, LGS( / Las (0) (T.pp Co A) (L.p( (A 1l2 The value of normalized
Los A Cos (0) is reported in Figure g
Amazon-Photo
Wik-CS
PubMed
1.05
1.0
1.00
0.9
Lastd) min Lasl
Lestd) min LeylA)
0.95
min LoylA)
0.8
min Lax
0.6
0.90
0.7
20 Iteration
Iteration
Iteration
Figure 8: The value of relative spectral change Las ( (0) when maximizing the spectrum norm (orange) or minimizing it (blue) via Eq. 7
Based the graph spectral theory, the eigenvalues are bounded within [0, 2]. thus the L2-norm of the graph spectrum is also bounded by the total number of nodes, For example, the values of the original spectrum norm (O) for Cora, Amazon-Photo, Wiki-CS and PubMed are 24.88, 22.13, 22.13,31.7. 31.79, and 65.26 respectively. From Figure 8 we can observe that maximizing Las ( (A) indeed results in an larger spectrum norm compared with the original graph (i.e. Las( A) Las (0) 1), while minimizing it achieves a smaller spectrum norm (i.e. Los Las (0) < 1).
E EXTENSION TO SUPPORT MORE AUGMENTATION TYPES
Table 13: Graph classification performance using node dropping augmentation schemes on the GCL instantiation in Figure 2
The metric is accuracy%. %.
Biochemical Molecules
Social Networks
Dataset
NCI1
PROTEINS
COLLAB
IMDB-M
Uniformly random node dropping
69.27 1: 0.86
73.40 1 0.74
75.19 1 0.67
53.04 - 0.63
Spectral guided node dropping
70.96 1 0.77
74.51 1 0.58
75.65 1 0.55
53.77 = 0.61
The proposed principle from the graph spectral perspective can also be extended node dropping augmentation. We design a soft node dropping scheme, which assigns a dropping probability to each node. Different from the edge perturbation scheme, node dropping is sampled from a Bernoulli distribution B(p), where p E [0, 1J". We can sample a node dropping vector d E {0, 13", where d; (p) indicates whether to drop the node i, and the node dropped d;
Dropping node is equivalent to removing all the edges connected to this node. Therefore, we can extend the operation of node dropping to edge removal. The node dropping probability implics the following edge removing probability matrix P:
P p 1T
(16)
2
where 1 is an all-one vector with dimension n. The node dropping based augmentation scheme can be then obtained by:
T(A) A + (-A)
(17)
where o is an dlement-wise product. To optimize the node dropping probability vector p. we can follow Eq. 5 by replacing the edge perturbation scheme A Co A with the node dropping scheme:
max |eig(Lap((A + (-A) e P)) eig(Lap(A)))) PES
(18)
26

---

Published as a conference paper at ICLR 2023
where S = fsis [0, ||s|[2 c) and controls the node perturbation strength. Following similar optimization step, the node dropping probability vector p can be obtained. Augmented views are then sampled from the optimized probability p to drop nodes.
We empirically compared the spectrum guided node dropping augmentation with uniformly random their prediction accuracy four graph classification datasets. We can still observe that the spectral guided node dropping augmentation achieves better performance, which demonstrates the applicability of our proposed principle both edge and node augmentation. To enable more general topology augmentation, the spectral distance of two graphs can be further extended from L2 distance distribution divergence, such Wasserstein distance, to capture the distributional change of graph spectrum.
node dropping strategy.
27


Reviews:
[{"review_id": "yK2g68E38Xv", "reviewer": "Reviewer_SvG5", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposed one spectral augmentation scheme for graph contrastive learning methods. It aims to preserve the spectral invariance which is related to the large changes in the graph spectrum. The experiments demonstrate the effectiveness of the proposed method.\n\n", "summary_of_the_review": "This paper proposed one spectral augmentation scheme based on the structural invariance. Extensive experiments demonstrate the effectiveness of the proposed method. There exist one question when evaluate the flipped edges as mentioned before.", "strength_and_weaknesses": "Strength:\nThis paper combines structural invariance with spectral analysis, which is interesting and reasonable for graph contrastive learning.\n\nWeaknesses:\nThe sensitive edges that can change the graph property should be emphasized when considering the structural invariance. While the spectral augmentations are designed based on the whole graphs, and the edge perturbation is designed for each edge, i.e., the edge flipping is independent. \nThen, does this mean that the flipped edges are all sensitive when learning structural invariance? How to evaluate these edges independently? Besides, it would be better to show the influence of different $\\epsilon$ in Eq.(3). ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "sHGzpoNmhm", "reviewer": "Reviewer_eFML", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a new way to augment the graph-structured data through the analysis of the graph spectrum. Based on the observation that the augmentation changing graph structure dramatically can improve the performance of graph learning, the authors propose a way to find the edges that can dramatically change the spectrum of a graph. The modified graphs are used to augment graph datasets. The experiments are conducted on various datasets for node-level and graph-level classifications. The proposed method induces a significant performance improvement in most cases.\n", "summary_of_the_review": "The paper is well-written and easy to follow. The technical details are well provided. The extensive amount of experiments well supports the main claim of the paper. Overall, I lean towards acceptance of this paper.", "strength_and_weaknesses": "Strength\n- The proposed idea of spectral augmentation is novel and technically valid.\n- The extensive experiments support the purpose of the spectral augmentation well. \n\nWeaknesses + Questions\n- Although spectral augmentation shows improved performance on many graph learning experiments, the way of changing the graph spectrum is somewhat counter-intuitive since the large changes in the graph spectrum imply large topological changes in the original graph. In that sense, it would be good to provide some qualitative examples of how the graph is augmented after spectral augmentation. for example, how do molecular graphs change after augmentation? do they still keep the important functional groups or not?\n- The selection of epsilon sounds important. It would be good to have some additional experiments on the analysis of the hyperparameter.\n- In experiments, the k-lowest and *highest* eigenvectors are used to augment. We often assume that the highest eigenvectors contain noisy information, and I wonder about the reason behind using the highest eigenvectors.\n- Although the eigendecomposition is only performed once for each graph, a graph such as Pubmed still requires a huge amount of time to compute. Will there be a huge difference if one employs some approximation of eigendecomposition?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "B5V9dS18EYH", "reviewer": "Reviewer_fWm4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper tackles the problem of how to design structural/topological augmentations for graphs, which can be used by graph contrastive learning. The authors aim to find a principled way for topology augmentations by exploring the invariance of graphs from the spectral perspective. This paper proposes to generate topological augmentations guided by maximizing the change in the spectral domain. Experiments on both graph- and node-level tasks demonstrate the\neffectiveness of the proposed method in graph self-supervised learning.", "summary_of_the_review": "Overall I recommend rejection for the current manuscript. My major concern is that several critical questions of the proposed spectral-augmentation approach are not discussed or explored, which limits the contribution of the paper and leaves confusion to the community. I would expect there is also some room to improve the experimental results further if the authors can rethink those important questions of spectral augmentation.", "strength_and_weaknesses": "#### Strengths\n1. The description and formulation of the proposed algorithm are clear, and I like the idea of measuring the topological change of graphs in the spectral space.\n2. The experiment results are extensive. I appreciate the authors not only compare many baselines under the graph contrastive learning setup but also consider the transfer learning and adversarial robustness problems.\n\n#### Weaknesses\n1. I like the idea of measuring the augmentation in the spectral space. The paper proposes a working algorithm, SPAN, by maximizing the L2 distance of eigenvalues and specifically modeling the edge modification/perturbation. But I think some important or highly-related questions in this direction are not sufficiently discussed and explored in this paper.\n    1. One important problem is why maximizing the perturbation (in terms of L2 distance of eigenvalues) can still/always generate valid views of the original graph? Is it necessary to require the $\\Delta$ matrix to be sparse (i.e., not too many 1's), and thus the perturbed graph is not too far from the original one? If the perturbed graphs (i.e., the two views generated by SPAN) are too far away from the original one (in terms of the L2 distance of eigenvalues), what topological information is still preserved, and are they still label preserving? \n    2. Due to complexity constraints, the authors propose to only compute the $K$ largest and smallest eigenvalues. The authors claim they are the most informative ones, but is there any reference or theory supporting this claim? From my experience, I think it is likely for the real-world graph to have many eigenvalues (of the symmetric normalized Laplacian) equal or close to 0 and 2, but the number of eigenvalues around 1 is relatively small. In this regard, if the chosen $K$ is much smaller than $n$, would it be likely the eigenvalues used to optimize the augmented graph is always equal or close to 0 and 2?\n    3. Since this paper only considered the L2 distance between eigenvalues. Thus we are forced to compare graphs of the same size. And only edge perturbation is considered. However, I think we can generalize to consider, e.g., a distributional divergence or two-sample distance, like empirical 1-Wasserstein distance, and generalize the framework to augmentations that also change the number of nodes (e.g., node dropping, subgraph cropping). If this direction is considered out of the scope of this current paper, then the contribution of this paper is somehow limited to a specific type of topological change on graphs and also kind of limit the overall contribution.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "6MX4iOKYSdc", "reviewer": "Reviewer_2d5T", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a topology augmentation method for graph contrastive learning which explores invariance of graphs from the spectral perspective. To realize the spectral invariance, the paper aims to identify sensitive edges whose perturbation leads to a large spectral difference. The conjecture is that the GNN encoder then focuses more on invariant spectral components. Numerical experiments illustrate the improvement in the performance of unsupervised representation learning, the generalization capability in transfer learning and induced robustness to adversarial attacks.", "summary_of_the_review": "The paper provides a novel augmentation approach for graph self-supervised learning. Extensive and carefully conducted experiments provide compelling evidence that the proposed method is effective for a range of tasks. The main weaknesses of the paper are  the absence of concrete definitions for key concepts such as \"structural invariance\", the somewhat weak linkage to \"spectral invariance\" and then the incorporation of methodological developments and approximations that lead to a final procedure that is relatively far from the initial motivation. ", "strength_and_weaknesses": " Strengths:\n1.    The approach for generating topology augmentations for GCL by perturbing edges in order to maximize the spectral change is novel.\n2.     The experimental analysis is extensive, spanning multiple tasks and including numerous datasets and baselines. \n4.     The appendices contain additional experiments that provide considerably more insight into the behaviour of the proposed approach and what aspects lead to the observed performance improvements.\n\nWeaknesses:\n1. Some key terms are vaguely defined. “Structural invariance” is defined as “preserv[ing] the essential structural properties” but it is not at all clear what these structural properties are. As a result, some claims in the paper are not well-supported. For example, there does not appear to be genuine support for the claim that “the information about the edges causing structural instability is minimized in the learned representations”.\n\n2.\tThe connection between structural invariance and spectral invariance is not solid. Yes, the spectrum is strongly related to many structural properties such as clustering, but there is not sufficient evidence here to state that “perturbing graph spectrum controls the change of structural properties”, at least not in the sense that there is a well-understood “control” of the change that is being induced. \n\n3.\tThe connection from equation (4) to equation (5) is not well-motivated. The initial argument is that a perturbation should be made to maximize the spectral change from the original graph. Then it becomes maximizing the spectral discrepancy between the two views. Finally it becomes maximizing and minimizing the spectral norms. The paper does not clearly explain why the last step aligns with the initial motivation.  \n\n4.\tThe computational cost of the proposed approach is high due to the eigendecomposition. To address this, the authors focus on the K lowest and highest eigenvalues. This takes the optimization task further away again from the initial motivation. The paper offers the vague argument that these “are the most informative suggested by spectral graph theory”, but there are no citations to support this claim, nor any clarification to explain what is meant by “most informative”. It is good that experimental results are included ot explore the impact of varying the number of included eigenvalues, but my concern is that by this point there has been a very significant migration from the initial motivation of preserving structural properties. \n\nMinor point: was there a check whether the normality assumption of the t-test is satisfied?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%