Rethinking Spectral Augmentation for Contrast-based Graph Self-Supervised Learning
Authors: Xiangru Jian
Xinjian Zhao
Wei Pang
Chaolong Ying
Yimu Wang
Yaoyao Xu
Tianshu Yu
Venue: Accepted by TMLR ()

Abstract: The recent surge in contrast-based graph self-supervised learning has prominently featured an intensified exploration of spectral cues. Spectral augmentation, which involves modifying a graph's spectral properties such as eigenvalues or eigenvectors, is widely believed to enhance model performance. However, an intriguing paradox emerges, as methods grounded in seemingly conflicting assumptions regarding the spectral domain demonstrate notable enhancements in learning performance. Through extensive empirical studies, we find that simple edge perturbations - random edge dropping for node-level and random edge adding for graph-level self-supervised learning - consistently yield comparable or superior performance while being significantly more computationally efficient. This suggests that the computational overhead of sophisticated spectral augmentations may not justify their practical benefits. Our theoretical analysis of the InfoNCE loss bounds for shallow GNNs further supports this observation. The proposed insights represent a significant leap forward in the field, potentially refining the understanding and implementation of graph self-supervised learning.

Published in Transactions on Machine Learning Research (02/2025)
Rethinking Spectral Augmentation for Contrast-based Graph Self-Supervised Learning
Xiangru Jian"
ziongr..jonnnuuateelo.co
Cheriton School of Computer Science University of Waterloo
Xinjian Zhao
sinjianzhao @tlink. edu.cc
School of Data Science
The Chinese University of Hong Kong, Shenzhen
Wei Pang"
u.yyang@wwatertoo.cm
Cheriton School of Computer Science University of Waterloo
Vector Institute
Chaolong Ying
School of Data Science The Chinese University Hong Kong, Shenzhen
Yimu Wang
yimu. www.wwwwwwwwtwwrrooooooo
Cheriton School of Computer Science University of Waterloo
Yaoyao Xu
wyyaoyaoBcukk.duu.com
School of Data Science The Chinese University of Hong Kong, Shenzhen
Tianshu Yu!
yutionshu@cuhk.ed...
School of Data Science
The Chinese Universily of Hong Kong, Shenzhen
Reviewed on OpenReview: https: // openreview. net/ forum? id= HrjpDpppppppp fa3
Abstract
The recent surge in contrast-based graph self-supervised learning has prominently featured an intensified exploration of spectral cues. Spectral augmentation, which involves modifying graph's spectral properties such as eigenvalues or eigenvectors, is widely believed to enhance model performance. However, intriguing paradox emerges, methods grounded in seemingly conflicting assumptions regarding the spectral domain demonstrate notable enhancements in learning performance. Through extensive empirical studies, we find that simple edge perturbations random edge dropping for node-level and random edge adding for graph-level self-supervised learning consistently yield comparable or superior performance while being significantly more computationally efficient. This suggests that the computational overhead of sophisticated spectral augmentations may not justify their practical benefits. Our theoretical analysis of the InfoNCE loss bounds for shallow GNNs further supports this observation. The proposed insights represent significant leap forward in the field, potentially refining the understanding and implementation of graph self-supervieed learning.
"Xiangru Jian, Xinjian Zhao, and Wei Pang contributed equally this paper. i "Corresponding author

---

Published in Transactions on Machine Learning Research (02/2025)
1 Introduction
In recent years, graph learning has emerged as a powerhouse for handling complex data relationships in multiple fields, offering vast potential and value, particularly in domains such as data mining Haamilton et al.
2017), computer vision (Xu et al., 2017), network analysis (Chen et al. 2020b). and bioinformatics (Jin et al,
2018 However, limited labels make graph learning challenging to apply in real-world scenarios. Inspired
by the great success of Superviedd Learning (SSL) in other domains (Devlin et al. 2018 Chen al.) 2020ah, Graph Sell-Supervised Learning (Graph SSL) has made rapid progress and has shown promise by achieving state-of-the-att performance many tasks (Xie et al., 2022), , where Contrast- Graph SSL (CG-SSL) are most dominant (Liu et al., 2023 This type of method is grounded in the concept of mutual information (MI) maximization. The primary goal is to maximize the estimated MI between augmented instances of the same object, such as nodes, subgraphs, or entire graphs. Among the new developments in CG-SSL, approaches inspired by graph spectral methods have garnered significant attention. A prevalent conviction is that spectral information, including the eigenvalues and eigenvectors of the graph's 's Laplacian,
plays a crucial role in enhancing the efficacy of CG-SSL (Liu et al. 2022a Ko et al. 2023 Lin al. 2023
Yang ct al. 2023 Chen et al. 2024
In general, methods in CG-SSL can be calegorized into two types based on whether augmentation is performed on the input graph to generate different views (Chen et al. 2024). i.e. augmentation based and augmentation-frco mothods. Of the two, the augmentation- based mothods are more predominant and widely
studied (Hassani & Khasahmaadi 2020 Liu et al. 2023 You et al. 2020 Liu et al. 2022a Lin et al. 2023
Yang al.) 2023). Specifically, spectral augmentation has received sigmificant attention, as it modifies a graph's spectral properties. This approach is believed to enhance model performance, aligning with the proposed importance of spectral information in CG-SSL. However, there scems consensus on the true effectiveness of spectral information in the previous works proposing and studying spectral augmentation. SpCo (Liu et al. 2022a) introduces the general graph augmentation (GAME) rule, which suggests that the difference in high-frequenc, parts between augmented graphs should be larger than that of low-froquency parts. 2023) contends that effective topology augmentation should prioritize perturbing sensitive odges that have a substantial impact on the graph spectrum. Therefore, a principled augmentation method is designed by directly maximizing spectral change with a certain perturbation budget, without mentioning any specific domain of spectrum. GASSER. (Yang et al., 2023) selectively perturbs graph structures based on spectral cues to better maintain the required invariance for contrastive learning frameworks. Specifically, it aims to augment the graphs to preserve task-relevant frequency components and perturb the irsk-irrelevant ones with care. While all three related methods are segeeentation-basel and share in the set of CG-SSL frameworks like GRACE (Zhu et al. 2020) and MVGRL (Hassani & Khasahmadij 2020), a contradiction emerges among these related works on spectral augmentation: while SPAN advocates for maximizing the distance between the spectrun of augmented graphs regardless of spectral domains, SpCo and GASSER argue for the preservation of specific spectral components and domains during augmentation. The consistent. performance gain derived from opposing methodical designs naturally raises our concern:
SPAN [Lin et al.
Are spectral augmentations necessary in contrast-based graph SSL?
Given the question, this study aims to critically evaluate the effectiveness and significance of spectral augmentation in contrast-based graph SSL frameworks (CG-SSL). With evidence-supported claims and findings in the following sections, we show that despite their computational complexity, sophisticated spectral augmentations do not demonstrate clear advantages over simple edge perturbations. Our extensive experiments reveal that straightforward edge perturbations consistently achieve superior performance while being significantly more computationally efficient. Our theoretical analysis on the InfoNCE loss bounds for shallow GNNs provides additional insights into understanding this phenomenon and supports our claims. We elaborate our findings through a series of studies carried out in the following efforts:
In Sec. 4 we demonstrate that shallow networks consistently achieve better performance in CG-SSL, analyze their inherent limitations capturing global spectral information, and provide theoret- ical bounds on the InfoNCE loss that help explain the limited benefits of sophisticated spectral augmentations compared to simple edge perturbation.
2

---

Published in Transactions on Machine Learning Research (02/2025)
2. In Sec 5 claim that simple edge perturbation techniques, like adding edges to dropping edges from the graph, not only compete well but often out outperfrrm spectral augmentations, without any significant help from spectral cues. To support this,
(a) In Sec. [ overall model performance on test accuracy with four state-of-the-art frameworks on both node- and graph-level classification tasks support the superiority of simple edge perturbation. (b) Studies in Sec. 7.1 reveal the indistinguisaabiiiyy between the average spectrum of augmented graphs from edge perturbation with optimal parameters on different datasets, no matter how different. that of original graphs is, indicating GNN encoders can hardly learn spectral information from augmented graphs. That is to say, edge perturbations can not benefit from spectral information. (c) In Sec. 7.2 we analyze the effectiveness of trate-of-thh-ar" spectral angmentation baseline (i.e., SPAN) by perturbing odges to alter the spectral characteristics of augmented graphs from simple edge perturbation augmentation and examining the impact on model performance. As it turns out, the results show no performance degradation, indicating the spectral information contained in the augmentation is not significant to the model performance.
(d) In Appendix E.3 E.3 statistical analysis is carried out to argue that the major reason edge perturbation works well is not because of the spectral information as they are statistically not the key factor on model performance.
2 Related work
coutrast-based Graph Sele-Supervised (CG-SSL). CG-SSL learning alleviates the limitations of supervisod learning, which heavily depends on labcled data and often suffers from limited generalization (Liul et al. 2022b). This makes it a promising approach for real-world applications where labeled data is scarce. CG-SSL applies a variety of augmentations to the training graph to obtain augmented views. These augmented views, which are derived from the same original graph, are treated as positive sample pairs sets. The key objective of CG-SSL is to maximize the mutual information between these views to learn robust and invariant representations. However, directly computing the mutual information of graph representation is challenging. Hence, in practice, CG-SSL frameworks aim to maximize the lower bound of mutual information using different estimators such as InfoNCE (Gutmann & Hyvärinen] 2010), Jensen-Shannol (Nowozin et al., 2016), and Donsker-Varee Varadhan (Belghazi et al. 2018). For instance, frameworks like GRACE (Zhu et al.] 2020).
GCC (Qiu et al. 2020), and GCA (Zhu et al. 2021b) utilize the InfoNCE estimator their objective function. On the other hand, MVGRL (Hassani & Khasahmadi 2020) and InfoGraph (Sun et al. 2019) adopt the Jensen-Shannon estimator. Some CG-SSL methods explore alternative principles. G-BT (Bielak et al. 2022) extends the redundaancy-rdduction principle by decorrelating representations between two augmented views to prevent feature collapse. BGRL (Thakoor et al., 2021) adopts a momentum-driven Siamese architecture, using node feature masking and edge modification as augmentations to maximize mutual information between online and target network representations.
Graph Augmentations in CG-SSL. Beyond the choice of objective functions, another crucial aspect of augmentation-basee methods in CG-SSL is the selection of augmentation techniques. Early work by (Zhu agnostic heuristic graph augmentation for CG-SSL, such as edge perturbation, attribute masking, and subgraph sampling. These straighttorward and effective methods have been widely adopted in subsequent CG-SSL frameworks due to their demonstrated success (hhkkorr et al.] 2021 Yu et al. 2024). However, these domain-agnostic graph augmentations often lack interpretability, making it difficult understand the exact impact of these augmentation, on the graph structure and learning outcomes. To address this issue, MVGRL (Hassani & Khasahmadi 2020) introduces graph diffusion
et al. 2020) and (You et al. 2020) introduced several
augmentation strategy, where the original graph provides local structural information and the diffused graph offers global context. Morcover, three spectral augmentation methods-SpCo (Liu et al., 2022a)), GASSER (Yang el al., 2023), and SPAN QLin et al., 2023) stand out by offering design principles based on spectral graph theory, focusing on how to enhance CG-SSL performance through spectral manipulations. However, our explorations show that these methods are unable to consistently outperform heuristic graph augmentations such as edge perturbation (DroPEDGE or ADDEDGE) in terms of performance under fair comparisons, and thus the design principles of graph augmentation still require further validation.
3

---

Published in Transactions on Machine Learning Research (02/2025)
3 Preliminary study
Contrast-based graph self-supervised learning framework. CG-SSL captures invariant features of graph by generaling multiple views (lypically two) through augmentations and then maximixing the mutual information between these views (Xie et al. 2022). This approach is ultimately used to improve performance
on various downstream tasks. Following previous work (Wu ct al.) 2021: Liu et al. 2022b; Xic et al. 2022 we first denote the generic form the augmentation T and objective functions Lat of graph contrastive learning. Given a graph 9 (A, with adjacency matrix and feature matrix X, the augmentation is defined as the transformation function T. In this paper, we are mainly concerned with topological augmentation, in which feature matrix X remains intact:
A T(A,)) =
In practice, two augmented views of the graph are generated, denoted as g( (AT, and g( = (T, The objective of GCL is to learn representations by minimizing the contrastive loss La between the augmented views:
arg min (po (0cu) 5o (g13)))
0* x-
(2)
0.6
where fe represents the graph encoder parameterized by 0, and Pe is projection head parameterized by ø. The goal is to find the optimal parameters 8" and 6" that minimize the contrastive loss.
In this paper, we utilize four prominent CG-SSL frameworks to study the effect of spectral: MVGRL, GRACE, BGRL, and G-BT. MVGRL introduces graph diffusion as augmentation, while the other three frameworks use edge perturbation as augmentation. Each framework employs different strategies for its contrastive loss functions. MVGRL and GRACE use the Shann-n and InfoNCE estimators as object functions, respectively. In contrast, BGRL and G-BT adopt the BYOL loss (Grill et al. 2020) and Barlow Twins loss (Zbontar et al. 2021), which are designed to maximize the agreement between the augmented views without relying on negative samples. More details of the loss function can be found in the Appendix C
Graph spectrum & Definition and application of spectral augmentation. We follow the standard
definition of graph spectrum in this study, details of which can be found in Appendix B Among various
augmentation strategies proposed to enhance the robustness and generalization of graph neural networks, spectral augmentation has been considered a promising avenue (Lin et al. 2023 Liu et al., 2022a Bo et al. 2023 Yang ct al., 2023). Spectral augmentation typically involves implicit modifications to the cigenvalues of the graph Laplacian, aiming at enhancing model performance by encouraging invariance to cerlain spectral properties. Among them, SPAN achieved state-of the--rttth--rttt performance in both node classification and graph classification. In short, SPAN elaborates two augmentation functions, Ti and T2, where Ti maximizes the spectral norm in one view, and To minimizes it the other view. Subsequently, these two augmentations are implemented in the four CG-SSL frameworks mentioned above (Strict definition in Appendix BB. The paradigm used by SPAN aims to allow the GNN encoder to focus on robust spectral components and ignore the sensitive edges that can change the spectral drastically when perturbed.
4 Limitations of spectral augmentations
Limitations of shallow GNN encoders in capturing spectral information. Multiple previous studies indicate that shallow, rather than deep, GNN encoders can be effective in graph self-supervised learning. This might be the result of overfitting commonly witnessed in standard GNN tasks. We have also carried out many empirical studies with range of CG-SSL frameworks and augmentations to support this idea in contrast-based graph SSL. As the most commonly applicd GNN encoder in CG-SSL (You et al. 2020 Yu et al. 2024 Guo et al.) 2024 Lin et al.) 2024), an empirical study on the relationship between the depth of GCN encoder and learning performance is conducted and results are presented in Fig. [ From that, we can conclude that shallow GCN encoders with or layers usually have the best performance. Note that this tendency not clear on graph-level tasks, which can be partially explained by the beneficial oversmoothing phenomenon present in this context, (Sothhenn et al. 2024). It. suggests that while deep encoders may have
4

---

Published in Transactions on Machine Learning Research (02/2025)
theoretically better expressive power than shallower ones, the limited benefits of deeper GNN architectures in the current CG-SSL practice imply that more layers may not bring significant improvements and could even hinder the quality of the learned graph representations.
Cora
0.00
PUbMed
Accuracy
Accuracy
0.50
0.33
0.76
0.79
077
0.78
0.06
Number of GCN Encoder Layers
Number of GCN Encoder Layers
Number of GCN Encoder Layers
(a) G-BT on node CLS
(b) MVGRL on node CLS
(c) SpCo+GRACE on node CL.
Average Accuracy
Average Accuraci
0.80
0.74
0.78
RRDTENN BINARY
0.72
PRUTLINS INDB BINARY
0.66
0.00
Number of GNN Encoder Layers
Number of GNN Encoder Layers
(d) G-BT graph CLS
(e) MVGRL on graph CLS
Figure 1: Accuracy of CG-SSL vs. number of GCN layers node and graph classification on four datasets.
(a) G-BT on node classification. (b) MVGRL on node classification. (c) SpCo+GRACE on node classification. (d) G-BT on graph classification. (e) MVGRL on graph classification. We choose two representative datasets for each task, iee. CORA and CITESEER for the node-level and PROTEINS and IMDB-BINARY for the graph-level classification. The evaluation protocol, along with dataset details and other experimental settings, are provided in Section 6.1
By design, most GNN encoders primarily aggregate local neighborhood information through their layered structure, where each layer extends the receptive field by one hop. The depth of a GNN critically determines its ability to integrate information from various parts of the graph. With only a limited number of layers, a GNN's receptive field restricted to immediale neighborhoods (e-g., 1-hop or 2-hop distances). This limitation severely constrains the network's ability to assimilate and leverage broader graph topologies or global features that are essential for encoding the spectral properties of the graph, given the definition of the graph spectrum.
Limited implications for spectral augmentation in CG-SSL. Given the inherent limitations of shallow GNNs in capturing spectral information, the utility of spectral augmentation techniques in graph self-super learning settings warrants scrutiny. While spectral augmentation techniques modify the graph's 's spectral components (e.g., eigenvalues and eigenvectors) may be limited if the primary encoder a shallow GNN cannot effectively process these spectral properties. To formally validate this intuition, establish the following theoretical analysis.
enrich the training process, their benefits
Theoretical Analysis of InfoNCE Bounds. To better understand the effectiveness of augmentations in shallow GNNs, we derive the following theoretical bounds on InfoNCE loss:
Thcorem (InfoNCE Loss Bounds). Given a graph G with minimum degree dman and marimum degree dmax: and its augmentation g' with local topological perturbation strength 8, for k-layer GNN with ReLU aclivation and weight matrices salisfying || [|(()) || < Iww, and assuming that the embeddings are normalized
5

---

Published in Transactions on Machine Learning Research (02/2025)
Alzz1l ||z||||| = 1), the InfoNCE loss satisfies with high probability:
2 ('22 /r
) =
62/T
-log 21/T + (n 1)e-
LinjoNca(C,9") log
(3)
/T
2
+ (n 1)ed17
e
where is as defined in Lemma 5 and e' is as defined in Lemma 6 Detailed descriptions of notations can be found in Table C The proof of Theorem and all related Lemmas can be found in Appendir D
This theoretical result reveals that the InfoNCE loss naturally stays within narrow interval given perturbation strength, regardless of augmentation complexity. Such finding helps explain why sophisticated spectral augmentations may not significantly outperform simple ones in shallow architectures. While the polential benefits of coupling spectral augmentations with deeper GNN architect ures
ures remain an open question.
Numerical Estimation and Interpretation. To illustrate the derived bounds, we provide numerical estimation of the upper and lower bounds based on realistic parameters for 1-layer GNNs (which is the case for best performance for several benchmarks presented in Sec. 6 later). As detailed in Appendix D.5 the parameters were chosen using typical graph augmentation scttings and realistic assumptions about and c' derived from Lemma 5 and Lemma 6 The resulting bounds on the InfoNCE loss are: Lower bound: 4.7989, Upper bound: 5.4497. The difference between the two bounds is 5.4497 - 4.7989 = 0.6508, indicating that the InfoNCE loss remains tightly constrained under these settings. This small interval suggests that shallow GNNs cannot fully utilize complex spectral augmentations, as their expressive capacity limits the potential variation in mutual information captured from augmented views. Our analysis reveals critical insight: the limited efficacy of spectral augmentation stems from the inability of shallow GNNs to effectively capture and leverage the spectral properties of graph. Instead, the learning outcomes are more directly influenced by simpler factors, such as the strength of edge perturbations. These findings reinforce the practicality of straight.forwnt augmentation methods like edge dropping and adding, which perform comparably or better in this constrained thcoretical setting.
5 Edge perturbation is all you need
So far, findings indicate that spectral augmentation is not particularly effective in contrast-based graph self-supervised learning. It may suggest that spectral augmentation essentially amounts to random topology perturbation, based on inconsistencies in previous studies (Lin et al. 2023 Liu et al. 2022a Yang et al.) 2023) and the theoretical insight that shallow encoder can hardly capture spectral properties. In fact, most of the spectral augmentations basically perform edge perturbations on the graph with some targeted directions. Since we preliminarily conclude that is quite difficult for those augmentations to benefit from the spectral properties of graphs, it is very intuitive hypothesize that edge perturbation itself matters in the learning process.
Consequently, we are turning back to Edge Perturbation (EP), more straight.orward and proven method for augmenting graph data. The two primary methods of edge perturbation are DROPEDGE and ADDEDGE. We want to claim that edge perturbation has a better performance than spectral augmentations and prove empirically that none them actually or even can benefit much from any spectral information and properties. Also, we demonstrate edge perturbation much more efficient practical applications for both time and space sake, where spectral operations are almost infeasible. Overall, we will support the idea with evidence in the following sections that simple edge perturbation is not only good enough but even very optimal in CG-SSL compared to spectral augmentations.
Edge perturbation involves modifying the topology of the graph by either removing or adding edges at random. We detail the two main types of edge perturbation techniques used in our frameworks: edge dropping and edge adding.
Edge dropping is the process of randomly removing subset of edges from the original graph create an augmented view. Adopting the definition from (Rong al. 2020). let (A, () be the original
DropEdge.
6

---

Published in Transactions on Machine Learning Research (02/2025)
graph with adjacency matrix A. We introduce mask matrix M of the same dimensions as A, where each entry My follows Bernoulli distribution with parameter 1 - (denoted as the drop rate). The edge-dropped graph G' is then obtained by element-wise multiplication of A with M (where @ denotes the Hadamard product):
A A
(4)
AddEdge. Edge adding involves randomly adding subset new edges to the original graph to create an augmented view. Let N be an adding matrix of the same dimensions as A, where each entry Ny follows a Bernoulli distribution with parameter q (denoted as the add rate), and Niy = 0 for all existing edges in A.
The edge-added graph G" is obtained by adding N to A:
A" A+N
(5)
These two operations ensure that the augmented views g()) and g(2) have modified adjacency matrices A' and A" respectively, which are used to generate contrastive views while preserving the feature matrix X.
5.1 Advantage of edge perturbation over spectral augmentations
Edge perturbation offers several key advantages over spectral augmentation, making it more elfective and practical choice for CG-SSL. Compared to spectrum-relatee augmentations, it has three major advantages.
Thcoretically intuitive. Edge perturbation inherently simpler and more intuitive. It directly modifics the graph's structure by adding or removing edges, which aligus well with the shallow GNN encoders' strength in capturing local neighborhood information. Given that shallow GNNs have limited receptive field, they are better suited to leveraging the local structural changes introduced by edge perturbation rather than the global changes implied by spectral angmentation.
Significantly better efficiency. Edge perturbation methods such as DROPEDGE and ADDEDGE are computationally efficient. Unlike spectral augmentation, which requires costly eigenvalue and eigenvector computations, edge perturbation can be implemented with basic graph operations. This efficiency translates faster training and inference times, making it more suitable for large-scale graph datasets and real-time applications. As shown in T the time and space complexity of spectrum-related calculations are several orders of magnitude higher than those of simple edge perturbation operations. This makes spectrum-related calculations impractical for large datasets typically encountered in real-world applications.
Table 1: Time and space complexity of different methods (Empirical Time is on PUBMED dataset)
Method
Time Complexity
Space Complexity Empirical Time (s/epocth
Spectrum calculation
(n
((n²)
26.435
DROPEDGE
(mm)
(m))
0.140
ADDEDGE
((m)
((m)
0.159
Optimal lcarning performance. Most importantly and directly, our comprehensive empirical studies indicate that edge perturbation methods lead to significant improvements in model performance, as presented and analyzed in Sec. 6 From the results there, the conclusion can be drawn that the performance of the proposed augmentations not only better than those of spectral augnentations but also matches or even surpassos the performance of other strong benchmarks.
These advantages position edge perturbation self-supervised learning. In the following section, we will present experimental analysis, demonstrating the accuracy gains achieved through edge perturbation methods.
robust and efficient method for graph angmentation in
6
Experiments on SSL performance
6.1 Experimental Settings
Task and Datasets. We conducted extensive experiments for node-level classification on seven datasets:
CORA, CIEESBER, PURMED (Kipf & Welling 2016), PHOTO, COMPUTERS (Shchur al. 2018), COAUTHOR-
7

---

Published in Transactions on Machine Learning Research (02/2025)
CS, and COAUTHOR-PHY. These datasets include various types of graphs, such citation networks, co-purchase networks, and co-authored networks. Note that we do not include huge-scale datasets like OGBN (Hu et al. 2021) for the high complexity of spectral augmentations. While both DROPEDGE and ADDEDGE have lincar complexity that can easily run on those huge datasets, no spectral augmentation can scale to them. Additionally, we carried out graph-level classification on five dalasets from the TUDalasel. collection (Morris et al.) 2020), which include biochemical molecules and social networks. More details of these datasets be found Appendix A
Baselines. We conducted experiments under four CG-SSL frameworks: MVGRL, GRACE, G-BT, and BGRL (mentioned in See 3). using DROPEDGE, ADDEDGE, and SPAN (Lin et al. 2023) as augmentation strategies. Note that there are only three very relevant studies on spectral augmentation ion strategies of CG-SSL to the authors' best knowledge, i.e., SPAN, SpCo (Liu et al. 2022a) and GASSER. (Yang et al. 2023). Among them, GASSER does not have open-soureed code so we are not able to reproduce any related results, but we try our best to directly adopt the best performance reported in that study to ensure comparison possible. Also, SpCo is only applicable to node-level tasks and its implementation is not robust enough to generalize to all the node-level datasets and CG-SSL frameworks. Therefore, we manage to include the results of all the settings that it is feasible to do, which is its original sctting and the combination of GRACE and it. Given the infeasibility and inaccessibility of the two, we selected SPAN as a major baseline because it is robust and general enough to all the datasets and experimental settings while allowing the modular plug-and-play integration of edge perturbation methods, enabling a very direct angle to evaluate the effectiveness of the spectral augmentations compared much simpler alternatives. Besides the major baselines mentioned above, other related ones are added to clearly and comprehensively benchmark our work. For MVGRL, we also compared its original PPR augmentation. For the node classification task,
GCA (Zhu ct al. 2021b)
GMI PPeng et al. 2020), DGI (Velickovic et al. 2019), CCA-SSG (Zhang et al. 2021] and SpCo (Liu el al.
2022a as baselines. For the graph classification task, we use RGCL (Li et al., 2022 and GraphCL You
ct al. 2020 as basclines. Detailed experimental configurations are in Appendix A
Evaluation Protocol. We adopt the evaluation and split scheme from previous works (Veličković el al., 2019 Zhang et al., 2023 Lin et al. 2023). Each GNN encoder is trained with self-supervised learning. After training, we freeze the encoder and extract embeddings for all nodes or graphs. Finally, we train a simple linear classifier using the labels from the training/validdttinn validatiinio set and test it with the testing set. The accuracy of classification on the testing set shows how good the learned representations are. For the node classification task nodes are randomly divided into 10% 106100%/80 /80% for training, validation, and testing, and for graph classification datasets, graphs are randomly divided into 50%/10%/14 110%/0%% for training, validation, and testing.
6.2 Experimental results
We present the prediction accuracy of the node classification and graph classification tasks in Table 2 and Table 3 respectively. Our comprehensive analysis reveals distinct patterns in the effectiveness of different augmentation strategies across these two task types. For node classification, DropEdgE consistently achieves the best performance across multiple datasets and CG-SSL frameworks, demonstrating superior robustness and consistency. While ADDEDGE also achieves competitive accuracy, DROPEDGE stands out in this area. In graph classification, ADDEDGE frequently achieves the best performance across multiple datasets and CG-SSL frameworks, showing superior and more consistent results. The effectiveness of ADDEDGE in graph classification may be attributed to 'beneficial oversmoothing" In graph-level tasks, the convergence of node features to a common representation aligned with the global output can be advantageous. By polentially increasing graph density and the proportion of positively curved edges (Nguyen et al., 2023), ADDEDGE might facilitate this beneficial effect in graph classification tasks. Notably, all the results from SPAN as well as GASSER and SpCo generally underperform relative to both DROPEDGE and ADDEDGE while also encountering scalability issues on larger datasets and suffering from a high overhead of training time.
proposed by Southern et all (2024)
8

---

Published in Transactions on Machine Learning Research (02/2025)
Table 2: Node classification. Results of baselines with "t' are adopted directly from previous works. MV- GRL+PPR the original sctting of MVGRL. The best results in each cell are highlighted in grey The best results overall are highlighted with bold and underline. Metric is accuracy (%)
Mudel
CORA
CIrESBER
PUBMED
PROTO
COMPUTERS
COAUTHOR- CS
COAUTHOR: PBY
GCA!
83,67 1 0.44
71.48
0.26
78.87
0.49
92.33 = 0.16
88.94
= 0.15
93.10
0.01
95.68 0.05
GMI
83.02
0.33
72.45
1 0.12
79.94
1 0.25
90.68
1 0.17
52.21
1 0.31
91.08
1 0.56
DGI
82.34 0.64
71.85
0.74
76.82
0.61
91.61
1: 0.22
63.95
0.47
92.15
0.63
94.51
0.52
CCA-SSG
84.20 0.40
73.10
0.30
0.40
93.14
93.31 0.22
95.38
SpCo
83.78 0.70
71.82
1.26
80.86
GASSER!
85.27 0.10
75.41
0.84
83,00
0.61
93.17 = 0.31
88.67
0.15
MVGRL + PPR
83.33 1.19
71.56
1.89
84.13
0.26
88.47 + 1.02
89.84
0.12
90.57
0.61
OOM
MVGRL + DROPEDGE
84.31 = 1.95
74.85 = 0.73
85.62 + 0.45
89,28 1: 0.95
90.43
= 0.33
93.20
= 0.81
96,70 +: 0.28
MVGRL + ADDEDGE
83.21 1.65
73.65
1.60
84.86
1.19
87.15
1: 1.36
87.59
1 0.53
92.91
0.65
95.33 1. 0.23
MVGRL +SPAN
$1.77
73.65
85,21
0.99
88.75
92.25
0.76
OOM
MVGRL + GASSER!
80.36 0,05
74.18 0.73
80,80 0.19
G-BT + DROPEDGE
86.51
2.04
72.95
2.46
87,10
1.21
93.55 + 0.00
88.66
0.16
93.31
0.05
96.06
0.24
G-BT ADDEDGE
82.10 = 1.48
66.36
= 4.25
85,98 + 0.81
93.68 1: 0.79
57.81 = 0.79
91.98 = 0.66
96.51 + 0.02
G-BT SPAN
84.06 2.85
67.46
3.18
85.97 0.41
91.85
1. 0.22
58.73
0.62
92.63
0.07
OOM
GRACE + DROPEDGE
$4.19 2.07
75.44
0.32
87.84 0.37
92.62 + 0.73
86.67
93.15
0.23
OOM
GRACE + ADDEDGE
85.78 0.62
71.65
1.63
85,25
0.74
76.74
0.57
92-46 0.25
OOM
GRACE + SPAN
82.81 0.91
67.76
0.21
85.11 + 0.71
93.72 0.21
88.71
0.06
91.72 1.75
0OM
GRACE + GASSER!
84.10 0.26
74.17
+ 0.64
83,97 + 0.52
GRACE SyCo
81.61 0.75
1.47 70.83
84.97 1.13
BGRL, + DRoPEDGB
$3.21 3.29
71.46
0.56
86.25 0.13
92.90 + 0.69
91.58
0.18
95.29
BGRL + ADDEUGE
$1.19 1:21
69.06
1.34
84.54 0.22
91.85 0.75
86.75
1.15
91.78
0.77
95.29
0.09
BGRL + SPAN
$3.33 0.45
06.26
0.92
85,97 + 0.41
91.72 = 1.75
88.61
0.39
92.29
0.39
OOM
Table 3: Graph classification. Results of baselines with 'f' are adopted directly from previous works. MVGRI+PPR is the original setting of MVGRT. The best results in each cell are highlighted in grey The best results overall are highlighted with bold and underline. Metric is accuracy (%).
Model
MUTAG
PROTEINS
NCI1
IMDE-BINARY
IMDE-MULTI
GraphCL
86.80 1.34
74.39 0.45
77.87 # 0.41
71.14 # 044
48.58 0.67
RGCL!
87.66 1.01
75.03 0.43
78.14 + 1.08
71,85 + 0.84
49.31
0.42
GMCL
91.09 6.28
77.44 = 3.83
82.99 = 2.06
75.60 + 3.17
MVGRL PPR
90.00 5.40
78.92 = 1.83
78.78 + 1.52
71.40 + 1.17
52.13
1.42
MVGRL+ SPAN
93.33 2.22
79.81 + 2.45
77.56 + 1.77
75.00 + 1.09
51.20
+ 1.62
MVGRL+ DROFEDGE
93.33 = 2.22
78.92 + 1.33
77.81 + 1.50
76.40 + 0.48
51.46
+ 3.02
MVGRL+ ADDEDGE
94.44 + 3.51
81.25
3.13
77.27
+ 0.71
74.00 + 2.82
51.73
2.43
G-BT + SPAN
90.00 = 6.47
80.89
3.22
78.29 + 1.12
65.60 + 1.35
45.60 + 2.13
G-BT DROPEDGE
92.59
77.97
0.42
1.24
49.11
1.25
G-BT ADDEDGE
92.59 2
80.61 1.68
75.91 0.59
73.33
1.21
48.88
1.13
GRACE SPAN
90.00 4.15
79.10
2.30
78.49
0.79
70.90
+ 3.96
47.73
1.71
GRACE + DROPEDGR
88.88
3.51
78.21
1.92
76.93 + 1.14
71.00
1: 3.75
47.46 +: 3.02
GRACE AnnENGE
02.22 4.44
80.17 + 2.21
79.97 + 2.35
71.67
+ 2.36
49.86 +: 4.00
BCRL SPAN
90.00 4.15
79.28 + 2.73
78.05 + 1.62
72.40 + 2.57
47.46 + 4.35
BGRL + DROPEDGE
86.88 4.96
76.60 = 2.21
76.15 + 0.43
71.60
+ 3.31
51.47 = 3.02
BCRL- + ADDENGR
91.11 5.66
79.46 + 2.18
76.98 + 1.40
72.80
+ 2.48
47.77 + 4.18
6.3 Ablation Study
To validate our findings, we conducted series of ablation experiments on two exemplar datasets, CORA and MUTAG, representing node- and graph-level tasks, respectively. These ablation studies are crucial to rule out potential confounding variables, such as model architectures and hyperparameters, ensuring that our conclusions about the performance of CG-SSL are robust and comprehensive.
Number of Layers of GCN Encoder. To assess the impact of model depth, we conducted both nove-level and graph-level experiments using varying numbers of GCN encoder layers. This analysis to rule out the possibility that model depth, rather than augmentation strategies, influences the claim. As expected, the results, detailed in Appendix E.T show that deeper encoders generally lead to worse performance. This
9

---

Published in Transactions on Machine Learning Research (02/2025)
suggests that excessive model complexity may introduce noise overfitting, diminishing the benefits of spectral information. Therefore, our conclusion still holds tightly.
Type of GNN Encoder. While we initially selected GCN to align with the common protocols in previous studies for a fair comparison, we also explored other GNN architectures to ensure our findings are not specific to GCN alone. To further validate our results, we conducted additional experiments using GAT (Veličković let al. 2019) for both node- and graph-level tasks, as well as GP' (Rampášek et al.) 2024) for the graph-level task. As reported in Appendix E.2] the performance trends observed with GAT and GPS are consistent with those obtained using GCN. This consisteney across different encoder types further supports our conclusion that simple edge perturbation strategies are sufficient, and that spectral augmentation does not significantly enhance performance, regardless of the type of GNN encoder applied.
7 The insignificance of Spectral Cues
Given the superior empirical performance of edge perturbations mentioned in Sec. G one may still argue whether it is a result of some spectral cues or not, as all the analyses mentioned are not direct evidence of the insignificance of the spectral information in the study, To clarify this, we have three questions to answer, (1) Can GNN encoders learn spectral information from augmented graphs produced by edge perturbations? (2) Are spectra. in spectral augmentation necessary? (3) Is spectral information statistically a significant factor in the performance of edge perturbation? Given the questions, we conduct series of experimental
studies to answer them respectively in Sec. 7.1 7.2 and Appendix E.3
7.1 Degeneration of the spectrum after Edge Perturbation (EP)
Here we want to conduct studies to answer the question of whether the GNN encoders applied can learn spectral information from the augmented graph views produced by EP. Therefore, collect the spectrum of all augmented graphs ever produced along the way of the contrastive learning process of the best framework with the optimal parameter we have in this study, i.e., G-BT + EP with best drop rate or add rate d and calculate the average one for each representative dataset in this study for both node- and graph-level tasks. We find that though the average spectrum of those original graphs is strikingly different, that of augmented graphs is quite similar for node- and graph-level tasks, respectively. This indicates a certain degree of degeneration of the spectra they are no longer easy to separate after EP. Therefore, GNN encoders can hardly learn spectral information and properties between different original graphs from those augmented graph views. Note that, though we have defined some context of frameworks, this result is generally only dependent on the augmentation methods. We will elaborate on both the node-level and graph-level results in this section.
Node-Level Analysis. Here, we visualize the distributions of the average spectrum of graphs al the node level using histograms. The spectral distribution for each graph is represented by sorted vector of its cigenvalues. When referring to the average spectrum, we mcan the average over the eigenvalue vectors of each augmented graph. We plot the histograms of different spectra, normalized to show the probability density. Note that eigenvalues are constrained within the range [0, 2), as we adopted the commonly used symmetrical normalization. We analyze the spectral distributions of three node classification datasets: CORA, CITESEER, and COMPUTERS. We compare the average spectral propertics of both original and augmented graphs. The augmentation method used is DRopEngR applied with optimal parameters identified for the G-BT method. The results of the visualization are presented in Fig. 3 By comparing the spectrum distributions of original graphs for the datasets in Fig, 3a| we can easily distinguish the spectra of the three datasets. This contrasts with the highly overlapped average spectra of all the datasets, indicating the degeneration mentioned. To support this claim, we also present the comparison of the spectra of original and augmented graphs on all 3e respectively, to show the obvious changes after the edge perturbations.
three datasets in Fig. 3c 3d
and
Graph-Level analysis. For graph-level analysis, we basically follow the settings mentioned above in node-level onc. The only difference from the nodc-level task is that we have multiple original graphs with various numbers of nodes, leading to the inconsistent dimensions of the vector of the eigenvalues. Therefore, to provide more detailed comparison of spectral properties at the graph level, we employ Kernel Density
10

---

Published in Transactions on Machine Learning Research (02/2025)
Comparison of Spectrum Distributions
Comparison of Spectrum Distributions
2.5
MUTAG OG Mean KDE
MUTAG AUG Mean KDE
MUTAG-AUG
Probability Density
0.8
PROTEINS-OG Meen KDE
Probability Density
2.0
PROTEINS-AUG Mean KGE
PROTEINS OG Mean = Std Dev
PROTEINS AUG Mean 4 Std Dev
0.6
1.0
0.4
1.00
Eigenvalue
Eigenvalue
(a) Average spectra of original graphs
(b) Average spectra of augmented graphs
Comparison of Spectrum Distributions
Comparison of Spectrum Distributions
MUTAG-DD
PROTEINS OG Moan KDE
1.2
MUTAG-AAU
PROTEINS-AUG Mean KDE
Probabiityy Density
Probability Density
1.50
1.25
0.8
1.00
0.6
0.4
0.50
0.2
0.0
0.00
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
Eigenvalue
Eigenvalue
(c) The Spectrum of MUTAG
(d) The Spectrum of PROTEINS
Figure 2: The spectrum distributions of graphs on different graph classification datascts. MUTAG and PROTEINS are chosen as they are well representative of all the node classification datasets. OG means original graph and AUG means augmented graph. The augmentation method ADDEDGE with the best parameter on G-BT method.
Estimation (KDE) Parzen 1962) to interpolate and smooth the distributions of eigenvalues. We compare two groups of graph spectra. Each group's spectra are processed to compute their KDEs, and the mean and standard deviation of these KDEs are calculated.
We analyze the spectral distributions two node classification datasets: MUTAG and PROTEINS. We compare the average spectral properties of both original and augmented graphs. The augmentation method used is ADDEDGE as is the better among EP methods, applied with optimal add rate identified for the G-BT method.
Like the results in node-level analysis, in Fig. and 2b witness the obvious difference between the average spectra of original graphs while the significant overlap between those of augmented graphs, especially if pay attention to the overlapping of the area created by the standard deviation of KDEs. Again, this contrast is not trivial because of the striking mismattc between the average spectra original and augmented graphs in both datasets, as presented in Fig, 2c and 2d
7.2 Spectral Perturbation
To further destruct the spectral properties from model performance, we introduce Spectral Perturbation Augmentor (SPA) for finer-grate greined anatomy. SPA performs random edge perturbation with an empirically negligible ratio TsPA to transform the input graph into a new graph GSPA, such that and ISPA are close each other topologically, while being divergent in the spectral space. The spectral divergence dsPA between G and GSPA is measured by the Lg-distance of the respective spectra. With properly chosen hyperparameters
11

---

Published in Transactions on Machine Learning Research (02/2025)
Spectrum Distributions
Spectrum Distributions
10
Cora-OG
Cora-AUG
2.5
CiteSeer-OG
CiteSeer-AUG
Probabliity Density
Probability Density
Computers-OG
Computers-AUG
2.0
1.5
1.0
0.5
0.0
Eigenvalue
Eigenvalue
(a) Spectrum of original graphs
(b) Spectrum of augmented graphs
Spectrum Distributions
Spectrum Distributions
Spectrum Distributions
Core-OG Core-AUG
GteSeer-OG CteSeer-AUG
Computers-Cu OG Computers-AUS
Probabiity Denstty
Probobiitty Deesity
Probabiity
8.5
Eigancallu
2.00
1.50
3.5
0.0
0.58
Eigenvalus
1,00
1.25
3.50
3.75
9.0
1.50
Eigenvale
1.00
1.50
1.75
(c) Comparison on CORA
(d) Comparison on CITESEER
(e) Comparison on COMPUTERS
Figure 3: The spectrum distributions of graphs on different node classification datasets. CORA, CITESEER, and COMPUTERS are chosen as they are well representative all the node classification datasets. OG means original graph and AUG means average augmented graphs. The augmentation method is DROpEDCE with the best parameter G-BT method.
TSPA and dSPA, we view the augmented graph GSPA as a doppelganger of G that preserves most of the graph-proximin with only spectral information eliminated.
Spectral perturbation on spectral augmentation basclines. SPAN, being a statc-of-the-art spectral augmentation algorithm, demonstrated the correlation between graph spectra and model performance through designated perturbation spectral priors. However, the effectiveness of simple edge perturbation motivated us to further investigate whether such relationship is causational.
Specifically, for each pair of SPAN augmented graphs G²,9², we further augment them into GSPA SAPA with our proposed SPA augmentor. The SPA-augmented training performed under the same setup as SPAN, with graphs being SPA-aaummented graphs GSPA. Results Fig I show that the effectiveness of graph augmentation can be preserved and, in some cases improved, even if the spectral information is destroyed.
SPAN, along with other spectral augmentation algorithms, be formulated parameterized 2-step generative process:
optimization
SSPAN Po (SSPAN Go), OSPAN Pa (SSPAN SSPAN)
Given the properly that GSPA is lopologically close to GSPAN and the performance function P f (9), limg-+GerAN P (g) (GSPAN), which indicates the continuity around GSPAN, we make a reasonable assertion that GSPA comes from the same distribution as GSPAN- However, with their spectral space being enforced to be distant, GSPA is almost impossible to be sampled from the same spectral augmentation generative process:
dsPA
pe (SSPA (o) -
Pa.a (GsPA (9))
Although the constrained generative process Eq. does indicate some extent causality between spectral distribution S and the speetral-augmented graph distribution GSPAN, our experiment challenges
12

---

Published in Transactions on Machine Learning Research (02/2025)
essential and fundamental aspect of such reasoning: such causality exists upon pre-defined generative processes, which does not intrinsically exist in the graph distributions. Even worse, such constrained generative process is incapable of modeling the full distribution of ISPAN itself. In our experiment setup, all GSPA serve as strong counter examples.
Spectral Perturbation
Spectral Perturbation
Accuracy
Accuracy
Chesser ORI
PROTEINS
Cruseer SPA
PROTEINS sMA
MVGRL
061
GRACE
BGRL
MVGRL
Gd1
GRACE
BGRL
Frameworks
Frameworks
(a) Node classification
(b) Graph classification
Figure Comparison of SPAN performance before and after applying SPA. After severely disrupting the spectral, the performance of SPAN is still comparable to that of the original version.
8 Conclusion
In this study, we investigate the effectiveness of spectral augmentation in contrast-based graph self self-supervised learning (CG-SSL) frameworks to answer the question: Are spectral augmentations necessary in CG-SSL? Our findings indicate that spectral augmentation does not significantly enhance learning efficacy. Instead, simpler edge perturbation techniques, such as random edge dropping for node-level tasks and random edge adding for graph-level tasks, not only compete well but often outperform spectral augmentations. To specific, we demonstrate that the benefits spectral augmentation diminish with shallower networks, and edge perturbations yield superior performance in both node- and graph-leve classification tasks. Also, GNN encoders struggle to learn spectral information from augmented graphs, and perturbing edges alter spectral characteristics does not degrade model performance. Furthermore, our theoretical analysis (Theorem [ reveals that the InfoNCE loss bounds the mutual information achievable by angmentations, highlighting that the relatively limited direct contribution of spectral augmentations compared to simpler edge perturbations, especially when in shallow GNNs. These results challenge the current emphasis on spectral augmentation, advocating for more forwgh and effective edge perturbation techniques CG-SSL, potentially refining the understanding and implementation of graph self-supervised learning.
References
Mohamed Ishmael Belghazi, Aristide Baratin, Sai Rajeshwar, Sherjil Ozair, Yoshua Bengio, Aaron Courville, and Devon Hjelm. Mutual information neural estimation. In International conference machine learning, pp. 531-540. PMLR, 2018.
Piotr Bielak, Tomasz Kajdanowicz, and Nitesh V Chawla. Graph barlow twins: A self-supervised representation learning framework for graphs. Knowledge- Based Systems, 256:109631, 2022.
Deyu Bo, Yuan Fang, Yang Liu, and Chuan Shi. Graph contrastive learning with stable and scalable spectral encoding. In Shirth-seventh Conference on Newral Information Processing Systems, 2023. URL
https://openreviiee
Jingyu Chen, Runlin Lei, and Zhewei Wei. PolyGCL: GRAPH CONTRASTIVE LEARNING via learnable spectral polynomial filters. In The Twelfth International Conference on Learning Representations, 2024. URL http:p///ppppaeeeeeeeeeeee/////s
13

---

Published in Transactions on Machine Learning Research (02/2025)
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International conference machine learning, pp. 1597-1607. PMTR, 2020a.
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph ncural networks count substructures? Advances in neural information processing systems, 33:10383 10395, 2020b.
Fan RK Chung. Spectral graph theory, volume 92. American Mathematical Soc., 1997.
Jacob Devlin, Men Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. orXiv preprint urXiv:1810.0 04800, 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 supe-supe learning. Advances in neural information processing systems, 33:21271 21284, 2020.
Xiaojun Guo, Yifei Wang, Zeming Wei, and Yisen Wang. Architecture matters: Uncovering implicit mechanisms in graph contrastive learning. Advances in Newral Information Processing Systems, 36, 2024.
Michael Gutmann and Aapo Hyvärinen. Noise-contrastive estimation: A new estimation principle for unnormalized statistical models. In Proceedings of the thirleenth international conference on artificial intelligence and statistics, pp. 297 304. JMLR Workshop and Conference Proceedings, 2010.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi-view representation learning on graphs. International conference on machine learning, pp- 4116-4126. PMLR, 2020.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datascts for machine learning on graphs, 2021. URL
Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. In International conference on machine learning, pp. 2323 2332. PMLR, 2018.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprinl XrXi:: 02907, 2016.
Taewook Ko, Yoonhyuk Choi, and Chong-Kwon Kim. Universal graph contrastive learning with novel laplacian perturbation. In Uncertainty in Artificial Intelligence, pp. 1108-1108. PMLR, 2023.
Sihang Li, Xiang Wang, An Zhang, Yingxin Wu, Xiangnan He, and Tat-Seng Chua. Let invariant rationale discovery inspire graph contrastive learning. In International conference on machine learning, pp. 13052- 13065. PMLR, 2022.
Lu Lin, Jinghui Chen, and Hongning Wang. Spectral augmentation for self-supervised learning on graphs. The Fleventh International Conference Learning Representations, 2023. URL https://openree
Minhua Lin, Teng Xiao, Enyan Dai, Xiang Zhang, and Suhang Wang. Certifially robust graph contrastive learning. Advances in Neural Information Processing Systems, 36, 2024.
Nian Liu, Xiao Wang, Deyu Bo, Chuan Shi, and Jian Pei. Revisiting graph contrastive learning from the perspective of graph spectrum. In Alice H. Oh, Alckh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022a. URL hntts:///ppereviee..rr forum?id:=L007TUWRR XI
14

---

Published in Transactions on Machine Learning Research (02/2025)
Yixin Liu, Ming Jin, Shirui Pan, Chuan Zhou, Yu Zheng, Feng Xia, and S Yu Philip. Graph self-supervised learning: A survey. IEEE transactions on knowledge and dala engineering, 35(6)58879 5900, 2022b.
Yixin Liu, Ming Jin, Shirui Pan, Chuan Zhou, Yu Zheng, Feng Xia, and Philiip S. Yu. Graph self-supervised learning: A survey. IEEE Transactions Knowledge and Data Engincering, (100):577955000 2023. doi: 1ALL00//TKDE222223117999
Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. arXiv preprint #Xix:2007.08663 2020.
Khang Nguyen, Nong Minh Hieu, Vinh Duc Nguyen, Nhat Ho, Stanley Osher, and Tan Minh Nguyen. Revisiting over-smoothing and over-squashing using ollivier-rici curvature. In International Conference on Machine Learning, pp. 25979. PMLR, 2023.
Sebastian Nowozin, Botond Cseke, and Ryota Tomioka. f-gan: Training generative neural samplers using
variational divergence minimization. Advances in neural information processing systems, 29, 2016.
Emanuel Parzen. On estimation of a probability density function and mode. The anmals of mathematical statistics, 3363)110651 1962.
Zhen Peng, Wenbing Huang, Minnan Luo, Qinghua Zheng, Yu Rong, Tingyang Xu, and Junzhou Huang. Graph reprosentation learning via graphical mutual information maximization. In Proceedings of The Web Conference 2020, pp. 270, 2020.
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-training. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 1150 1160, 2020.
Ladislav Rampášek, Mikhail Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for a general, powerful, scalable graph transformer. In Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS '22 Red Hook, NY, USA, 2024. Curran
Associates Inc. ISBN 9781713871088.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks node classification. In International Conference Learning Representations, 2020. URL
https::/openreviee net/forum? ?dd Hdxkiikgrrkkk
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint 1tf:::8811.05866 2018.
Joshua Southern, Francesco Di Giovanni, Michael Bronstein, and Johannes Lutzeyer. Understanding virtual nodes: Oversmoothing, oversquashing, and node heterogeneity. arXiv preprint arXiv:2405. 13526, 2024.
Fan- Yun Sun, Jordan Hoffmann, Vikas Verma, and Jian Tang, Infograph: Unsupervised and semi-supervised graph-level representation learning via mutual information maximization. arXiv preprint arXiv: 010000 2019.
Shantanu Thakoor, Corentin Tallec, Mohammad Gheshlaghi Azar, Rémi Munos, Petar Veličkovié, and Michal Valko. Bootstrapped representation learning on graphs. In ICLR 2021 Workshop on Geometrical and Topological Representation Learning, 2021.
Petar Velickovic, William Fedus, William L Hamilton, Pictro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph inforax. ICLR (Posler), 2(3):4, 2019.
Petar Veličković, William Fedus, William L. Hamilton, Pictro Liò, Yoshua Bengio, and R Devon Hjelm.
Deep graph infomax. In International Conference on Learning Represenlations, 2019. URL https //ppnneview httpe/vvew.eee//orreee netf/forumidrrk119lee..
Crike Von Luxburg. A tutorial on spectral clustering. Statistics and computing, 17:395 416, 2007.
15

---

Published in Transactions on Machine Learning Research (02/2025)
Lirong Wu, Haitao Lin, Cheng Tan, Zhangyang Gao, and Stan Z Li. Self-supervised learning on graphs: Contrastive, generative, or predictive. JEEE Transactions on Knowledge and Data Engineering, 35(4): 4216 4235, 2021.
Yaochen Xie, Zhao Xu, Jingtun Zhang, Zhengyang Wang, and Shuiwang Ji. Self-supervised learning of graph neural networks: A unified review. IEEE transactions pattern analysis and machine intelligence, 45(2): 2412 2429, 2022.
Danfei Xu, Yuke Zhu, Christopher B Choy, and Li Fei-Fei. Scene graph generation by iterative message passing. In Proceedings of the IEEE conference compuler vision and pallern recognition, pp. 5410-540 0411-,,4 2017.
Kaiqi Yang, Haoyu Han, Wei Jin, and Hui Liu. Augment with care: Enhancing graph contrastive learning with selective spectrum perturbation, 2023.
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. Advances in neural information processing systems, 33:5812 5823, 2020.
Yue Yu, Xiao Wang, Mengmei Zhang, Nian Liu, and Chuan Shi. Provable training for graph contrastive learning. Advances in Neural Informalion Processing Systemss 36, 2024.
Jure Zbontar, Li Jing, Ishan Misra, Yann LeCun, and Stéphane Deny. Barlow twins: Self-supervised learning via redundancy reduction. In International conference on machine learning, pp.
PMLR, 2021.
Hengrui Zhang, Qitian Wu, Junchi Yan, David Wipf, and Philip Yu. From canonical correlation analysis lo self-supervised graph neural networks. Advances in Neural Information Processing Systems, 34:76 1966--9,45 2021.
Yifei Zhang, Hao Zhu, Zixing Song, Piotr Koniusz, and Irwin King. Spectral feature augmentation for graph contrastive learning and beyond. In Proceedings of the AAAT Conference on Artificial Intelligener, volume 37, pp. 11289 11297, 2023.
Ziyan Zhang, Bo Jiang, Jin Tang, and Bin Luo. Unifying graph contrastive learning via graph message augmentation. arXiv preprint arXiv:2401.03633 2024.
Tong Zhao, Wei Jin, Yozen Liu, Yingheng Wang, Gang Liu, Stephan Günnemann, Neil Shah, and Meng Jiang. Graph data augmentation for graph machine learning: survey, arXiv preprint 2XXx:2202.0887. 2022.
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep graph contrastive representation learning. arXie preprint arXiv:2006. 041..,0111111.11 2020.
Yanqiao Zhu, Yichen Xu, Qiang Liu, and Shu Wu. An empirical study of graph contrastive learning. NewrIPS, 2021a.
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, pp. 2069-2080, 2021b.
16

---

Published in Transactions on Machine Learning Research (02/2025)
Contents
Introduction
2
Related work
3
3 Preliminary study
4
Limitations of spectral augmentations
4
5
Edge perturbation is all you need
6
5.1
Advantage of edge perturbation over spectral augmentations
7
6
Experiments SSL performance
7
6.1
Experimental Settings
7
6.2
Experimental results
8
6.3
Ablation Study
9
7
The insignificance of Spectral Cues
10
Degencration of the spectrum after Edge Perturbation (EP)
10
7.2
Spectral Perturbation
11
Conclusion
13
Dataset and training configuration
18
B Preliminaries of Graph Spectrum and SPAN
19
C Objective function of GCL framework
19
D Theoretical analysis
21
Notations
21
Detnitions and Preliminaries
21
D.3
Lemmas
22
0.4
Main Theorem
28
0.5
Numerical Estimation
28
0.6
Discussions on T'heorem
30
D.6.1
Positioning of Theorem
30
D.6.2
Connections to Spectral Augmentations
D.6.3
Coverage of Theorem
30
D.7
Empirical Verilication of InfoNCE Bounds
31
17

---

Published in Transactions on Machine Learning Research (02/2025)
E
More experiments
31
Effect of numbers of GCN Layers
31
Effect of GNN encoder
31
F.3
Relationship between spectral cues and performance of FI
E.3.1 Statistical analyses on key factors on performance of EP
34
E 0
Comparison with feature augmentation
37
A Dataset and training configuration
The node classification datasets used in this paper include the CORA, CITESEER, and PUBMED citation networks (Kipf & Welling) 2016), well as the PhoTo and COMPUTERS co-purchase networks (Shchur use the COAUTHOR-CS and COAUTHOR-PHY co-author relat venship networks. The statistics of node-level datasets are present in Table 4 The graph classification datasets include: The MUTAG dataset, which features seven types of graphs derived from 188 mutagenic compounds; the NCI1 dataset, which contains compounds tested for their ability to inhibit human lumor cell growth; the PROTEINS dataset, where nodes correspond to socondary structure elements connected they are adjacent in 3D space; and the IMDB-BINARY and IMDB-MULTI movie collaboration datasets, where graphs depict interactions among actors and actresses, with edges denoting their collaborations in films. These movie graphs are labeled according to their genres. The statistics of graph-level datasets are present in Table 5 All datasets can be accessed through PyG library]
Datascts.
et al. 2018). Additionally,
All experiments are conducted using 8 NVIDIA A100 GPU.
Table 4: Statistics of node classification datasets
Datasct
#Nodes
#Edges
# #Features
# Classes
CORA 2,708
5,429
1,433
7
CITESEER
3,327
4,732
3,703
6
PUBMED
19,717
44,338
500
3
COMPUTERS
13,752
245,861
767
10
Рhoтo
7,650
119,081
745
8
COAUTHOR-CS 18,333
81,894
6,805
15
COAUTHOR--HY 34,493
247,962
8,415
5
Table 5: Statistics of node classification datasets
Dataset
#Avg. Nodes
#Avg. Edges
# Graphs
# #Caasses
MUTAG
17.93
19.71
188
PROTEINS
39.06
72.82
1,113
NCT1
29.87
32.30
4110
IMDB-BINARE 19.8
96.53
1,000
2
IMDB-MULTI 13.0
65.94
1,500
5
Training configuration. For each CG-SSL framework, we implement it based on (Zhu et al. 202 We use the following hyperparameters: the learning rate is set to 5 x 10-4, and the node hidden size is set to 512, the number of GCN encoder layer is set E {1, 21, For all node classification datasets, training epochs are set E (50, 100, 150, 200, 400, 1000), and for all graph classification datasets, training epochs are set E (20,40) 40, ..., 2003. To achieve performance closer to the global optimum, we use randomized search determine the optimal probability of edge perturbation and SPAN perturbation ratio. For CORA and
htt. http:///hhabbbccc//yyytttt//111
18

---

Published in Transactions on Machine Learning Research (02/2025)
CITESEER the search is conducted one hundred times, and for all other datasets, it is conducted twenty times. For all graph classification datasets, the batch size is set to 128.
B Preliminaries of Graph Spectrum and SPAN
Given a graph G (A, X) with adjacency matrix A and feature matrix X, we introduce some fundamental concepts related to the graph spectrum.
Laplacian Matrix Spectrum The Laplacian matrix L of graph is defined
L=D-A
where D is the degree matrix, a diagonal matrix where each diagonal element Dj represents the degree of vertex i. The eigenvalues of the Laplacian matrix, known as the Laplacian spectrum, are crucial understanding the graph's structural properties, such as connectivity and the number of spanning trees (Chung 1997).
Normalized Laplacian Spectrum The normalized Laplacian matrix Lnorm is given by:
Lyorm D D-11/LD 1/2
The eigenvalues of the normalized Laplacian malrix, referred to the normalized Laplacian spectrum, are often used in spectral clustering (Von Luxburg to account for varying vertex degrocs.
2007) and other applications where normalization is necessary
SPAN The core assumption of SPAN is to maximize the consistency the representations of two views with large spectrum distance, thereby filtering out edges sensitive to the spectrum, such edges between clusters. By focusing more stable structures relative to the spectrum, the objective of SPAN can be formulated as:
max |/eig (L1) eig (L2)
TI. TES
where the transformations Ti and To convert A to A₁ and A2, respectively, producing the normalized Laplacian matrices L1 and Lg. Here, S represents the set of all possible transformations, and the graph spectrum can be calculated by eig (L).
C Objective function of GCL framework
Here brielly introduce the objective functions of the four CG-SSL frameworks used in this paper, for more detailed discussion about objective functions including other graph contrastive learning and graph
self-supervised learning frameworks which can refer to the survey papers [ic et al. 2022 Wu et al. 2021
Liu et al. 2022b We use the following notations:
ps: Projection head parameterized by ø.
h hy: Representations of the graph nodes.
by Representations of negative sample nodes.
P: Distribution of positive sample pairs.
F.; Distribution of negative sample pairs.
B: Set of nodes in batch.
(1) (2), Node representation matrices of two views.
19

---

Published in Transactions on Machine Learning Research (02/2025)
GRACE uses the InfoNCE loss to maximize the similarity between positive pairs and minimize the similarity between negative pairs. InfoNCE, loss encourages representations of positive pairs (generated from the same node via data augmentation) to be similar while pushing apart the representations of negative pairs (from different nodes). The loss function ΣNCE denotes as:
(Po()))
LNCE (po (h,, hy)) -E pxpx log epo(h.,hy) EnEN (Po().
(9)
MVGRL employs the Jensen-Shanon Estimator (JSE) for contrastive learning, which focuses on the mutual information between positive pairs and negative pairs.JSE maximizes the mutual information between positive pairs and minimizes for negative pairs, thus improving the representations' alignment and uniformity, The loss function LISE denotes as:
LISE (p+ (h,, h,)) = Ex [log (1 Pø (h,, (h,, Ep [log (p& (h, hy))
(10)
BGRL utilizes a loss similar to BYOL, which does not require negative samples. It uses two networks, an online wetwork and a target network, to predict one view from the other:
[ps (h:)) hy LBYOL (po (h,, hy)) = Epxp Il (h:)ll [byي]|
(11)
G-BT applies the Barlow Twins' loss to reduce redundancy in the learned representations, thereby ensuring better generalization:
2
CBT H
H(2))
-BB-P18
(12)
Eies
ib
H
11) in
H 1b
20

---

Published in Transactions on Machine Learning Research (02/2025)
D Theoretical analysis
D.1 Notations
Table 6: Notations and Definitions
Notation
Definition
g (V.8)
Original undirected graph, where V is the set of nodes and & is the set of edges. Perturbed graph obtained from via local topological perturbations. Number of nodes in the graph.
G'
= [
E
node in the graph.
9
k-hop subgraph around node v in G. Set of edges the subgraph C
E(G))
1 (E(
Number of edges in the subgraph G
Number of nodes in the subgraph G
Bv de, d'
Degrees of node in G and G', respectively. Minimum and maximum degrees in the k-hop subgraphs. Adjacency matrix of g and the adjacency matrix of g respectively. Adjacency matrix of g' and the adjacency matrix of g respectively. Degree matrix of G and the degree matrix of g respectively.
dmin; dmax A, A
A', A
D, D,D.
D', D',
Degree matrix of and the degree matrix of G respectively. Normalized adjacency matrices of G' and g' respectively.
A' annd A'v
X R
Node feature malrix, where do is the imput feature dimension.
Number of layers in the GNN and the size the k-hop neighborhood. Hidden representations at layer I in the GNN. Weight matrix at layer I in the GNN, with || S Lw. Upper bound on the spectral norm of the weight matrices.
H E Rexd
W(O) Rd txd
Lw
h. Rd
Embedding of node u after & GNN layers G. Embedding of node after & GNN layers in g'.
h Rd
P Rd,xd
Projection matrix applied to node embeddings obtain final representations. Final embedding of node in & after projection.
2. Phg IRd
z. = Ph R
Final embedding of node in G' after projection. Embedding dimension of the final node representations.
d
Temperature parameter in the InfoNCE loss.
sim(u, v)
Cosine similarity between vectors and v, defined as sim(u, v) 1[ |
T
D.2 Definitions and Preliminaries
Definition (Local Topological Perturbation). For a k-layer GNN, the local topological perturbation strength defined as the maximum fraction of edge changes in any node's 's k-hop neighborhood:
E(C))
8 max DEV
(1)
(8(G))
where A denotes the symmetric difference of edge sets, and G' is the perturbed graph.
Definition 2 (InfoNCE Loss). For a pair of graphs (9,9), the InfoNCE loss is defined as:
exp (sim (Z., z..) /T) Σ log Eney exp (sim (zu. 2(,) /T)
LinfoNCe(G.G')= n NEV
(2)
where 2u and z', are embeddings of node u in and g' respectively, sim(-.-) is cosine similarity, T is temperature parmeler,, and [
21

---

Published in Transactions on Machine Learning Research (02/2025)
D.3 Lemmas
Lemma (Adjacency Matrix Perturbation). Given perturbalion strength 6, the change in adjacency malrices of the k-hop subgraph around any node v satisfies:
AA - A'll S E0
(3)
where d denote the k-hop subgraph around node in the original graph 9, with adjacency matria A and degree matric D,.. Evl is the number of edges in the k-hop subgraph G Similar notations for g too.
Proof. Each edge change affects two symmetric entries in the adjaceney matrix A, each with magnitude (since edges are undirected). Let m be the number of edge changes within g Then the Frobenius norm of the difference is:
|| A.
Σ 1
Auai A'rasl = 2m.
(4)
Since the number of edge changes m S 81Ey1, we have:
|| AGll= S (6
(5)
Lemma 2 (Degree Matrix Change). For any node v in g
dd d' < 8d
(6)
Moreover, for the degree matrices:
D D-1/2 1/2 - -D', 1/-1//1/
5 ó. nh
(7)
r
2 8)3/22
and
5
1/2
(8)
2 dmmin 5/3/2'
where ny is the number of nodes in the k-hop subgraph, and dmin is the minimam degree in the subgraph.
Proof. The degree of a node changes by at most åd, due to the perturbation:
dd d'1 S ddy.
(9)
Consider the function f(x) = x 112 which is convex for x > Using the mean value thcorem, for some & between du and d'
1/2 1/2 d, - 112 = (E.) - d',) = 50 3/2 (do d.)).
(10)
Since d, (1 d)dy, have Eu 2 (1 5)d, 2 (1 5)dmin- Thus,
1/1/ de 112 < 2((1 8) 8)dmin 33/2
dd,
dd,
(11)
2(1 - 0
3/2
Since d, dmax, and dmin S du, we have:
1/2 d, -1/2|
<
8d 8d
8
(12)
2(1 8)3/2 23/2
2 Vddin (1 - 8)3/2
The Frobenius norm computed as:
D. 1/2 1/2 - D' 1/2
Σ
d 1/2 d'
-1/2
<no 2 (1 8/3/2
2
(13)
22

---

Published in Transactions on Machine Learning Research (02/2025)
Therefore,
1-11/2 D -1/2 1
8y
(14)
2 dmii (1 0)3/2
Similarly, the spectral norm bound is:
D 1/2 - D' 11/2
2 S 2/ 5)3/2
8
(15)
Lemma (Bounded Change in Normalized Adjacency Matrix). Given graph 9 with minimum degree dmii= marimum degree dmax: and by nodes in the k-hop subgraph, and its perturbation g' with local topological perburbation strength 8, the change in the normalized adjacency matrix for any k-hop subgraph is bounded by:
v Vuylmax
(V5+ (1 (1-8)3/2
5
| - A,lls MA--A,ll-
(16)
dmin
Proof. We start by noting that the normalized adjacency matrix is given by A. A,D. difference between the normalized adjacency matrices is:
1/2
The
A - A' = 1, 1/2 D', "',''"A,,,'"""""
(17)
Add and subtract D, D,21/2
A,D,,
1/2
Å A D (A, A A 1/2 A 1/2 D/- A.D. D;
(18)
Let E = D. 1/2 A.D. 1/2 1/2 A A.D. 1/2 Then,
A, A = D 1A, A') + E.
(19)
First, we bound the first term:
- 1/2 - < ||A Abllr S
1 dmai
20
(20)
Since |8g1 < max we have:
V 20 I 2220
nydmaxx
v dnyymaax
(21)
Thus,
Von,dmax
D. 1/2 - A.))
(22)
dman
Next, we bound
E E| Note Ihat:
E (D-1/2 1/2 - D --' + D
(D 1/2 1/2
DD-11/2)
(23)
Therefore,
E $2 D-1/2 1/2 -D'--D-11 1/21/2
2 | D 1/1
(24)
Since || S 2 & Vnndmaac
|D/
<
Vomm and using the bound from Lemma for
D. 1/2 D 1-2
we have:
8
8 Svn,dmaxx
E 22
X / Ryydmax
(25)
2 dm (1 8)3/2
Vdmii dmiu (1 8)3/2
23

---

Published in Transactions on Machine Learning Research (02/2025)
Combining both terms:
mon
8
Vn,ddmax
5 (vo+ (1- 513/2
A Acllp 2
(26)
dmin
dmiu -1-5///2
dmin
Lemma 4 (GNN Output Difference Bound). For a k-layer Graph Neural Network (GNN) fo with ReLU activalion funclions and weight matrices salisfying || S Lw for all layers i, given two graphs G and g with local topological perturbation strength ö, the difference in GNN outputs for any mode v is bounded by:
h - h'll S k (ALw)* B |
(27)
where:
he and hy, are the embeddings of node u in G and G', respectively, after & GNN layers.
X is the node feature matria.
A nn,dmax dmin
8
B vō++ 8)3/2
The is the number of nodes in the k-hop subgraph around node v.
duin and dmax are the minimum and marimum degrees in the subgraph.
Proof. We will prove the lemma by induction on the number of layers I.
Base Case (1= 0). At layer I == 0, before any GNN layers are appliod, the embeddings are simply the input features:
X, H X.
(28)
Thus,
(0) H0)) 0.
(29)
This establishes the base case.
Inductive Step. Assune that for some 2 0, the following bound holds:
H HO/ <I(AW)) B 2|
(30)
Our goal is to show that the bound holds for layer + 1:
H - HU+
- $
141 B B|X
(31)
The outputs layer (1 + 1)
H ((+1) ReLU (ÂH"W!.) H = ReLU (A'HW
(32)
where:
24

---

Published in Transactions on Machine Learning Research (02/2025)
Á and Á' are the normalized adjacency matrices of the k-hop subgraphs around node in g and g', respectively.
W()) is the weight matrix of layer I, with || Lw-
Since ReLU 1-Lipschitz, we have:
H H $ A A'H
(33)
We can expand the difference as:
ÁHwwO - W = À (H H w + (À - A') H wi))
(34)
Bounding Ti. Using the submulliplicative properly of norms:
|Till - | H H
w
(35)
2
From properties of and (
A F A, (as shown below), |
S l-w-
(36)
Also, since |
H
H HOO
pr we have:
T3 pe S ALW
H H101
(37)
Bounding | The entries of A are:
Aij
Aij
(38)
dd,d
where Ag E (0, 1}, and di, dz 2 dmin- Therefore,
Aigl
5 dmin
(39)
The number of non-zero entries in À is most nydmax- Therefore,
Vnodmax A. dmin
A
(40)
Bounding Tz. Similarly, we have:
T2ll S A A H
W
(41)
From the perturbation analysis:
| - All AB.
(42)
To bound [ 2 we note that:
H
H
(43)
We bound HH recursively.
25

---

Published in Transactions on Machine Learning Research (02/2025)
Bounding H Ir- At each layer, the output is given by:
H = ReLU
(44)
Since ReLU is 1-Lipschitz and | S A, have:
(0)
s - s ALW [H
(45)
Recursively applying this bound from = 0 to I, and noting that 112001112 || we obtain:
H HO
(ALw)' lX||2-
(46)
Therefore,
H || - (ALw)' |x
(47)
Now we have:
T2lls I AB (ALw)' | Iw = A BLW |X|
(48)
Total Bound for HH H
Combining T1 and T2:
H (1-1) H(41)
< ALw H H')))
A BLW ||X||2
(49)
F
Recursive Relation. Let C
H H0O ||
F. The recursive relation is:
C++1 S ALw 1+ BL 1+1 |X
(50)
We will prove by induction that:
C S ((AL)) B|X
(51)
Base Case.
For I = 0, Co = O. which satisfies the bound.
Inductive Step. Assume the bound holds for I:
C < ((AL)) B||X
(52)
Then for + 1:
C411 S ALwCi - AL+1 BL'+" ||
S ALw (I(T B ||x|| l12) + 4+ BL 1+1 |X||
LA 1 B |X|| 2 + A 4 L' B |
(53)
=( 1++4 I B X 1/
=(I+ 1) (ALw) 1+1 B X||2
This confirms that the bound holds for I ++1 1.
For I = k; we have:
(R) (R)
S kALW)) B| >
(54)
F
26

---

Published in Transactions on Machine Learning Research (02/2025)
Since [h,
h1ll <
H
H we obtain:
b h'll S (ALw)" x|
(55)
This completes the proof.
Lemma 5 (Minimum Cosine Similarity for Positive Pairs). For embeddings z, and z' produced by linear projection of GNN outputs, with |zo|| = | 1, the cosine similarity satisfies:
2
sim (Zu, 2,,) 2
(56)
2
where
Vindmax yb (Vo+ (1 8)3/2
8
k(
Li ||X|| l2
|Pl
dman
(57)
and Oz is the lower bound on ||zo|| (whicc equals in this case).
Proof. The embeddings are computed as Ph, and z Pha- Then,
1z 2,11 P b holl-
(58)
Using the bound from Lemma 4, we have:
VRrdmmxx (Vo+ (1 8)3/2
8
||2, 2لم1 s
Liv |Xl1 [Pl12
(59)
dini
Since ||z0|| =||z||| 1, the cosine similarity satisfies:
2
sim (Zu: 2/,) =
2 1z -
2 -2,12
(60)
Lemma 6 (Refined Negative Pair Similarity Bound). Assuming that embeddings of different nodes are approrimately independent and randomly oriented in high-dimensional space, and that the embedding dimension d satisfies d > log n, we have, with high probability;
(61)
where
log n d
(62)
Proof. Since 2u and z are unit vectors in Rd and approximately independent for + v, the inner product (zv, 2.,) follows a distribution with mean zero and variance d' By applying concentration incqualities such as Hoeffding's inequality or the Gaussian tail bound, for any > 0:
d(c')² 2
P P([(zo, 2.,1 2 e) s 2exp
(63)
2 log Selecting d' V d
we get:
log d
2
P [(z 2/,i1
(64)
Using the union bound over all n(n 1) pairs, the probability that any pair violates this bound small when d >> log
27

---

Published in Transactions on Machine Learning Research (02/2025)
D.4 Main Theorem
Theorem 1 (InloNCE Loss Bounds). Given graph G with minimuun degree dmai and maximam degree. dmax. and its augmentation G' with local topological perturbation strength 8, for k-layer GNN with ReLU activation and weight matrices satisfying || I Lw, and assuming that the embeddings are normalized A|lz.ll = || = 1), the InfoNCE loss satisfies with high probobility:
('2 T
- -log 1//T + (n - 1 ) LinjaNca(C,9") - -log
e//T
(65)
2
+ (n 1)e
e
where as defined in Lemma 5 and é' as defined in Lemma
Proof. For the positive pairs (same node G and g'), from Lemma 5:
2 sim Ze. 2,) 2 2
(66)
For the negative pairs (different nodes),
from Lemma 6, with high probability:
sim (Z,, z(,' S é', Vu + v.
(67)
The InfoNCE loss for node is:
exp (sim (2n. 2/) TT)
c, - log exp (sim (Ze, z1,) /T) Eupor exp (sim (Zus (T)
(68)
For the upper bound on Lus we use the minimal positive similarity and maximal negative similarity:
2
1- /r
2
L. log
(69)
2
/r + (n 1)ee'7
For the lower bound on Cu, use the maximal positive similarity and minimal negative similarity:
2/T
L. - log e//r (n -
(70)
Since this holds for all nodes v, averaging over all nodes, obtain the bounds for (".
D.5 Numerical Estimation
assess how tight the bound is while keeping dman not too large (e.g., dmin = 10), let's perform a numerical estimation.
Suppose:
Number of nodes: 1000.
Embedding dimension: d 4096.
Minimum degree: d'in 10.
Maximum degree: dmax 30.
28

---

Published in Transactions on Machine Learning Research (02/2025)
Layer count: k
1.
Weight matrix norm: Lw 0.5.
Inpul feature norm: |X|| = 1.
Projection matrix norm: P|| 1.
Temperature: 0.5.
Local perturbation strength: 8 == 0.1.
Compute E:
Assuming n2 R 30,
Vyddmax
v30 30
9900
30,
Vn,ommax
30
3,
dmin
10
Vo v0.1 ~ 0.316228.
8
0.1
0.1
& 0.117121,
(1 8/3/2
(1 (1- 0.1)13
0.853814
8
V8
0.316228
0.117121 0.433349,
(1 8/3/2
x 3 x 0.433349
0.650.
Compute e':
2 2og n
13.8155
è
v0.003374 0.05805.
4096
Compute exponents:
For the upper bound:
2
2
1.5775,
0.05805
0.1161.
0.5
For the lower bound:
1
-6' 0.1161.
2,
7
Compute numerator and denominator for the upper bound:
Numerator 4.8426.
Denominator & 1126.8881.
Compute numerator and denominator for the lower bound:
29

---

Published in Transactions on Machine Learning Research (02/2025)
Numerator se 7.3891,
Denominator Ri 896.5990.
Compute the InfoNCE loss bounds:
4.8426
Cupper log
(o.(00003))4) 5.4497,
1126.8881
7.3891
Llower log
log(0.00824) 4. 4989.
896.5990
Interpretation. The numerical gap between the upper and lower bounds, calculated as 5.4497 - 4.7989 0.6508, notably narrow. This tight. interval highlights key observation: shallow GNNs face intrinsic challenges in effectively exploiting spectral enhancement techniques. This due to their restricted capacity to represent and process the spectral characteristics of graph, irrespective of the complexity of the spectral modifications applied. The findings suggest that tuning fundamental augmentation parameters, such perturbation strength, may exert a more pronounced influence on learning outcomes than intricate spectral alterations. While the theoretical rationale behind spectral augmentations well-motivated, their practical utility might only be realized when paired with deeper GNNs capable of leveraging augmented spectral information across multiple layers of message propagation.
D.6
Discussions on Theorem
In this section, we generally describe the claim we want conclude from Theorem 1 and explain its connection to spectral augmentations.
D.6.1 Positioning of Theorem
In general, Theorem offers a useful lens by showing that under common assumptions, the InfoNCE objective remains bounded within finite range regarding the magnitude of local topological perturbation. We also carry out empirical validation of our theoretical InfoNCE bounds in Appendix D.6. However, it should be noted that it is indirect to some extent to spectral augmentations, due to the inherent difficulty of providing direct theoretical proof that simultaneously addresses spectral information, InfoNCE training objective, and downstream tasks in CG-SSL.
D.6.2 Connections to Spectral Augmentations
Because spectral augmentations primarily target the graph's eigenstructure, they may not necessarily push the loss beyond these inherent bounds, where the loss critical to the optimization the CG-SSL and eventually to the performance of downstream tasks. Therefore, we view Theorem [ as an initial theoretical insight rather than definitive statement on the value of spectral augmentations. By highlighting that the InfoNCE loss is constrained, it adds context to why advanced augmentation schemes and simpler approaches may converge to similar performance levels. We remain optimistic that further theoretical and empirical investigations can deepen our understanding of how spectral perturbations, and graph augmentations, interact with contrastive objectives in CG-SSL.
D.6.3 Coverage of Theorem
Loss functions. Theorem specifically focuses on ostablishing bounds for the InfoNCE objective in shallow GNNs. We select InfoNCE due to its prominence and widespread adoption in contivs graph self-supervised learning (CG-SSL). While this theoretical result provides valuable insights into the behavior of InfoNCE-basse CG-SSL, should be noted that the bounds may not directly generalize other contrastive objectives. While potentially valuable, the analysis of other objectives falls outside the scope of our current work, which aims to establish foundational theoretical understanding of this widely-used objective.
30

---

Published in Transactions on Machine Learning Research (02/2025)
Number of layers of GNN encoder. Note that Theorem 1 is proposed specifically for shallow GNNs and does not claim to directly extend to deeper architectures. Nonetheless, our empirical results indicate that deeper GNNs can exhibit degraded performance in practice, which is consistent with real-world setups for spectral augmentation approaches as well (SPAN (Lin et al., 2023 uses 2 layers, SpCo (Liu et al.) 2022a has only layer and GASSER (Yang al. 2023 uses or layers). This outcome not surprising, since shallow GNN encoders are widely adopted by various methods in the domain of CG-SSL, mostly for the sake of empirical performance. At the same time, we acknowledge that more work can be done to explore, especially from the theoretical aspect, how deeper GNN architectures might be effectively coupled with spectral augmentations, as the interactions in that setting are far more complex than those considered in our current theoretical result for shallow layers.
D.7 Empirical Verification of InfoNCE Bounds
To empirically validate our theoretical bounds on the InfoNCE loss (Theorem 1) and investigate the necessity of spectral augmentations, we conduct extensive experiments across different datasets using GRACE with a two-layer GCN encoder in Fig- and one-layer GCN encoder in Fig. G We fix the edge dropping rate 0.3 and perform 100 independent runs with different random seeds. These multiple runs naturally induce various spectral changes through random edge perturbations, allowing us to examine how the InfoNCE loss behaves under a wide range of spectral variations.
Our experiments on MUTAG and PROTEINS datasets reveal that the InfoNCE loss exhibits remarkably stable behavior, with minimal variations across different runs. This stability persists despite the diverse spectral changes induced by random edge dropping, supporting our argument that complex spectral augmentations may be unnecessary simple edge perturbations already provide sufficient regularization.
Interestingly, on the dense IMDB datasel, we observe larger fluctuations in the InfoNCE loss during the middle stages of training, with variations occasionally exceeding 1.0. However, these fluetuations consistently converge to a narrow band during the final stages of training, aligning with our thcorctical predictions. It's worth noting that our experimental setup using a two-layer GCN with 1024-dimensional embeddings theoretically allows for wider bounds compared to the single-layer GCN with 4096-dimensional embeddings analyzed in our proof. The fact that the observed loss values remain well within our theoretical bounds suggests that our derivation provides conservative estimates of the actual constraints on the InfoNCE loss.
These empirical results strengthen our theoretical findings by demonstrating that even with the diverse spectral variations induced by random edge perturbations, the InfoNCE loss remains well-bounded. This suggests that explicit spectral augmentations may be redundant, as simple edge perturbations already provide effective regularization while being computationally more efficient.
E
More experiments
E.1 Effect of numbers of GCN Layers
We explore the impact of GCN depth on accuracy by testing GCNs with 4, 6, and 8 layers, using our edge perturbation methods alongside SPAN baselines. Experiments were conducted with the GRACE and G-BT frameworks on the Cora dataset for node classification and the MUTAG dataset for graph classification. Each configuration was run three times, with the mean accuracy and standard deviation reported.
Overall, deeper GCNs (6 and 8 layers) tend to perform worse across both tasks, reinforcing the observation that deeper architectures, despite their theoretical expressive power, may negatively impact the quality of learned representations. The results are summarized in Tables and
E.2 Effect of GNN encoder
To further validate the generality of our approach, we conducted additional experiments using different GNN encoders. For the node classification task, we evaluated the CORA dataset with GAT the encoder, while
31

---

Published in Transactions on Machine Learning Research (02/2025)
MUTAG
PROTEINS
DROPEDOE
25.0
DROFEDOT
22.5
5.0
loss
28.0
6.5
37.9
100
15c
$6
260
Epochs
Epochs
lozs
23.0
38.5
38.0
Epochs
Epochs
IMDB-MULTI
lo55
30-
Epechs
Figure 5: Empirical behavior of InfoNCE loss across different datasets with GRACE and two-layer GCN. We show the mean InfoNCE loss (solid blue line) and standard deviation (shaded area) over 100 independent runs with random edge perturbations (drop rate = 0.3). Results are presented for MUTAG, PROTEINS, IMDB-BINARY. IMDB-MULTI, and NC11 datasets using a two-layer GCN encoder. The loss values exhibit consistent convergence to stable ranges, even though each run induces different spectral variations through random edge dropping. While the dense IMDB dataset shows larger fluctuations during the middle stages of training, all datasets eventually exhibit well-bounded behavior, suggesting that simple edge perturbations provide sufficient regularization for contrastive learning.
for the graph classification task, we performed experiments on the MUTAG dataset using both GAT and GPS as encoders.
The results, presented in Tables 9 and 10 are shown alongside the results obtained with GCN encoders. These findings demonstrate that our simple edge perturbation method consistently outperforms the basclines, regardless of the choice of the encoder. This confirms that our conclusions hold across different encoder architectures, underscoring the robustness and effectiveness of the proposed approach.
32

---

Published in Transactions on Machine Learning Research (02/2025)
MUTAG
PROTEINS
DROPEDOE
DROFEDOT
5.5
4.0
100 Epochs
15c
15c
Epochs
lozs
23.0
38.0
Epochs
Epochs
IMDB-MULTI
28
Epechs
Figure 6: Empiriaal behavior of InfoNCE loss across different datasets with GRACE and one-layer GCN,
Table 7: Impact of GCN depth on node classification task on the CORA dataset. column is grey Metric is accuracy (%).
The best result of cach
MODEL
4
GBO+DDOPEDGE
83.531 1.48
82.06= 3.45
80.884 1.38
GBT +ADDEDGE
81.994
0.79
79.04= 1.59
79.41
1.98
GBT+SPAN
80.394 2.17
81.25= 1.67
79.41 1.87
GRACE+DROPÈDGE
82.351 1.08
82.47= 1.35
81.74t
2.42
GRACE -ADDEDGE
79.17
#1.35
78.80=
0.96
81.00+
0.17
GRACE+SPAN
80.15+t 0.30
80. 15 0.79
75.984 1.54
E.3
Relationship between spectral cues and performance of EP
Based on the findings obtained from See 7.1 is very likely that spectral information can not be distinguishable enough for good representation learning the graph. But to more directly answer the question of whether
33

---

Published in Transactions on Machine Learning Research (02/2025)
Table 8: Impact GCN depth on graph classification task on the MUTAG dataset. The best result of each column is in grey Metric is accuracy (%).
MODEL
4
8
GRT+DROPEDGE
90.74 + 2.61
88.88
4.53
88.88
7.85
GBT +ADDEDGE
94.44 + 0.00
94.44
4.53
94.44
4.53
GBT+SPAN
94.44 + 4.53
92.59
2.61
90.74
2.61
GRACE+
94.44 + 0.00
90.74 + 2.61
90.74 - 2.61
GRACE + +ADDEDGE
92.59 + 5.23
94.44
4.53
94.44 + 0.00
GRACE+SPAN
90.74 + 2.61
90.74
5.23
88.88 + 7.85
Table 9: Accuracy of node classification with different GNN encoders on CORA dataset. The best result of each column in grey. Metric is accuracy (%).
MODEL
GCN
GAT
MVGRL+SPAN
84.57 + 0.22
82.90 + 0.86
MYGRL++DROPEDGE
84.31 1.95
83.21 = 1.41
MVGRL +ADDEDGE
83.21 1.65
83.33 0.17
GBT+SPAN
82.84 + 0.90
83.47 + 0.39
GBT + DROPEDGE
84.19 + 2.07
84.06 = 1.05
GBT + ADDEDGE
85.78 + 0.62
81.49 + 0.45
GRACE + SPAN
82.84 + 0.91
82.74 + 0.47
GRACE DROPEDGE
84.19 + 2.07
82.84 + 2.58
GRACE + ADDEDGE
85.78 = 0.62
82.84 + 1.21
BGRL + SPAN
83.33 0.45
82.59
0.79
BGRL + DROPEDGE
83.21
3.29
80.88 +-2 1.08
BGRL + ADDEDGE
81.49 = 1.21
82.23 = 2.00
spectral cues and information play important role in the learning performance of EP, we continue to conduct statistical analysis to evaluate the influence of various factors the learning performance. The results turn out to be consistent with our claim that spectral cues are insignificant aspects of outstanding performance on accuracy observed in Sec.
E.3.1 Statistical analyses on key factors on performance EP
From statistical angle, we have few dimensions of factors that can possibly influence learning performance, like the parameters of EP (i.e. drop rate in DROPEDGE or add rate q in ADDEDGE) well as potential spectral cues lying in the argument graphs. Therefore, to rule out the possibility that spectral cues and information are significant, comparisons are conducted on the impact of the parameters of EP in the augmentations versus:
The average Ly-distance between the spectrum of the original graph (OG) and that of each augmented graph (AUG) which introduced by EP augmentations, denoted as OG-AUG.
The average Læ-distance between the spectra a pair augmented graphs appearing in the same learning epoch when having a two-way contrastive learning framework, like G-BT, denoted as AUG-AUG.
Two statistical analysos have boen carried out argue that the former more critical determinant and a more direct cause of the model efficacy. Each analysis was chosen for its ability to effectively dissect and compare the impact of edge perturbation parameters versus spectral changes.
34

---

Published in Transactions on Machine Learning Research (02/2025)
Table 10: Accuracy of graph classification with different GNN encoders on MUTAG dataset. The best result of each column is grey. Metric accuracy (%).
MODEL
GCN
GAT
GPS
MVGRL+SPAN
93.33 + 2.22
96.29
2.61
94.44 0.00
DROPDED
93.33 2.22
92.22
3.68
96.26
5.23
MVGRL +ADDEDGE
3.51 94.44
94.44
6.57
95.00
5.24
GBT+SPAN
90.00 + 6.47
94.44
+ 4.53
90.74 + 5.23
GBT + DROPEDGE
92.59 + 2.61
94.44
+ 4.53
94.44 4.53
GBT + ADDEDGE
92.59 + 2.61
92.59
2.61
94.44 4.53
GRACE + SPAN
90.00 + 4.15
96.29
+ 2.61
92.59 + 2.61
GRACE + DROPEDGE
88.88 - 3.51
94.44 - 0.00
94.44 + 4.53
GRACE + ADDEDGE
92.22 + 4.22
96.29
- 2.61
94.44 0.00
BGRL + SPAN
90.00 + 4.15
94.44
4.53
94.44 0.00
BGRL DROPEDGE
88.88 + 4.96
90.74
+ 4.54
92.59 - 5.23
BGRL + ADDEDGE
91.11 + 5.66
96.29
+ 2.61
96.29 + 2.61
Due to the high cost of calculating the spectrum of all AUGs in each epoch and the stability of the spectrum of the node-level dataset (as the original graph is fixed in the experiment), we perform this experiment on the contrastive framework and augmentation methods with the best performance in the study, i.e. G-BT with DROPEDGE that the smaller the graph, the higher the probability that the spectrum distance has significant influence on the graph topology.
node-level classification. Also, we choose the small datasets, CORA for analysis. Note
Analysis 1: Polynomial Regression. Polynomial regression was utilized to directly model the relationship between the test accuracy of the model and the average spectral distances introduced by EP. This method captures the linear, or non-linear influences that these spectral distances may exert on the learning outcomes, thereby providing insight into how different parameters affect model performance.
Polynomial regression of node-level accuracy over drop rate p in DROPEDGE, average spectral distance between OG and AUG (OG-AUG), and average spectral distance between AUG pairs (AUG-AUG). The method is G-BT and the dataset is CORA. The best results are in grey
Table 11:
Order of the regression
Regressor
R-squared t Adj. R-squared + F-statistic: f P-value
Drop rate p
0.628
0.621
81.12
6.94o-12
(i.. linear)
OG-AUG
0.388
0.375
30.45
1.35c-06
AUG-AUG
0.338
0.325
24.55
9.39e-06
Drop rate p
0.844
0.837
126.9
1.14e-19 19
2 (i.c. quadratic)
OG-AUG
0.721
0.709
60.78
9.23c-14
AUG-AUG 0.597
0.580
34.88
5.16c-10
The polynomial regression analysis in Table II highlights that the drop rate p is the primary factor influencing model performance, showing strong and significant lincar and non-lincar relationships with test accuracy. In contrast, both the OG-AUG and AUG-AUG spectral distances have relatively minor impacts on performance, indicating that they are not significant determinants of the model's efficacy.
Analysis 2: Instrumental Variable Regression. To study the causal relationship, we perform an Instrumental Variable Regression (IVR) to rigorously evaluate the influence of spectral information and edge perturbation parameters on the performance of CG-SSL models. Specifically, we employ a Two-Stage Least Squares (IV2SLS) method to address potential endogeneity issues and obtain unbiased estimates of the causal effects.
35

---

Published in Transactions on Machine Learning Research (02/2025)
In IV2SLS analysis, define the variables as follows:
Y (Dependent Variable): The outcome aim to explain predict, which in this case is the performance of the SSL model.
X (Explanatory Variable): The variable that we believe directly influences Y. It is the primary factor whose effect on Y we want measure.
Z (Instrumental Variable): A variable that is correlated with X but not with the error term in the Y equation. It helps to isolate the variation in X that is exogenous, providing means to obtain unbiased estimates of X's effect on Y.
In this specific experiment, we conduct four separate regressions to compare the causal effects of these factors:
1. (x = AUG-AUG, z = Parameter): Examines the relationship where the spectral distance between augmented graphs (AUG-AUG) is the explanatory variable (X) and edge perturbation parameters are the instrument (Z).
2. (X Parameter, Z AUG-AUG):
Examines the relationship where the edge perturbation parameters are the explanatory variable (X) and the spectral distance between augmented graphs (AUG-AUG) is the instrument (7).
(X = OG-AUG, z= Parameter): Examines the relationship where the spectral distance between the original and augmented graphs (OG-AUG) is the explanatory variable (X) and edge perturbation parameters are the instrument (Z).
4. (X = Parameter, Z = OG-AUG): Examines the relationship where the edge perturbation parameters are the explanatory variable (X) and the spectral distance between the original and augmented graphs (OG-AUG) is the instrument (Z).
Table 12: IV2SLS regression results for the node-level task. The parameter refers to the drop rate in DROPEDGE. The experiment comes in pairs for each pair of variables and the better result is marked in grey.
Variable settings
R-squared
F-statistic t Prob (F-statistic)
X AUG-AUG, ==
0.341
45.77
1.68c-08
Z - AUG-AUG)
0.611
47.85
9. 9.85e-09
X = OG-AUG,
0.250
40.22
7.51c-08
X kp 2 OG-AUG)
0.606
41.27
5.62 5.62e-08
The IV2SLS regression results for the node-level lask in Table 12 indicate that the edge perturbation parameters are more significant determinants of model performance than spectral distances. Specifically, when the spectral distance between augmented graphs (AUG-AUG) is the explanatory variable (X) and drop rate p are the instrument (Z), the model explains 34.19 1% of the variance in performance (R-squared = 0.341). Conversely, when the roles are reversed (X = p. 7 AUG-AUG), the model explains 61.1% of the variance (R-squared 0.611), indicating stronger influence of edge perturbation parameter p. A similar conclusion can be made when comparing OG-AUG and p.
Summary of Regression Analyses The analyses distinctly show that the direct edge perturbation parameters have a consistently stronger and more significant impact on model performance than the two types of spectral distances that serve as a reflection of spectral information. The results support the argument that while spectral information might have contributed to model performance, its significance is extremely limited and the parameters of the EP methods themselves more critical determinants.
36

---

Published in Transactions on Machine Learning Research (02/2025)
E.4 Comparison with feature augmentation
Although this paper primarily investigates the impact of spectral information and employs simple edge perturbation algorithms for comparison, it is still worthwhile to compare these algorithms with feature augmentation-based graph self-supervised lcarning methods (Zhao et al. 2022). For node-level tasks, a representative approach is DGI (Velickovic et al.) 2019), which uses row-wise shuffling of the node feature matrix as feature augmentation strategy. For graph-level tasks, we compare against more recent work, GCML (Zhang et al., 2024). which introduces message augmentation as a general framework for graph data (feature) augmentation.
Experimental results (Table 13 Table 14 suggest that simple edge perturbation algorithms outperform feature augmentation methods, including the recent GCML. However, we do not claim that edge perturbation is the best possible augmentation method for graph contrastive learning. Rather, our aim to demonstrate that straightforward topological augmentations can be as effective as as-if if not better than many complex, specially designed approaches, thereby offering insights for future rescarch on CG-SSL.
Table 13: Node classification. Results of baselines with 'f' are adopted directly from previous works. For EP, the result is selected from the best setup for the task. The best results are highlighted in grey The metric is accuracy (%).
Model
CORA
CITESEER
PURMED
PHOтO
COMPUTERS
COAUTHOR-CS
COAUTHOR PHy
EP DGI
86.51 = 2.04
75.44 + 0.32
87.84 + 0.37
93.68 + 0.79
90.43 + 0.33
93.31 +
96.06 0.24
82.34 + 0.64
71.85 0.74
76.82 + 0.61
91.61 + 0.22
83.95 + 0.47
92.15 + 0.63
94.51 + 0.52
Table 14: Graph classification. Results of baselines with 't' are adopted directly from previous works. For EP, the result selected from the best setup for the task. The best results are highlighted in grey. The metric is accuracy. (%).
Model
MUTAG
PROTEINS
NCII
IMDB-BINARY
IMDB-MULTI
EP
94.44 3.51
80.64
79.97 2.35
76.40
51.73 2.43
GMCL
94.09 + 6.28
77.44 = 3.83
82.99 + 2.06
75.60 + 3.17
37


Reviews:
[{"review_id": "5cDRvahp5k", "reviewer": "Reviewer_ykmD", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. It challenges widely held assumptions about spectral augmentation.\n2. It offers solid experimental validation across multiple datasets and tasks.\n3. It combines theoretical insights with practical findings.\n\n\nWeaknesses:\n\n1. How about comparing edge perturbations with other types of augmentations, like node feature perturbations.\n2. Can author provide more detailed connections between theorem 1 and the spectral augmentations?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper questions the importance of spectral augmentation in CG-SSL and shows that simple edge perturbations can match or outperform it while being more efficient. It also provides theoretical InfoNCE bounds and supports its claims with extensive experiments and ablation studies.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please refer to weaknesses", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ZwTDWs77f8", "reviewer": "Reviewer_ZUcv", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\nOverall, this paper presents significant observations about the (in-)effectiveness of spectral augmentations. The experiments consider four different CG-SSL frameworks as well as node- and graph-level tasks and show that the main observations are consistent across these. The additional ablation studies in Section 7 are also insightful to the reader.\n\n**Weaknesses**\n\nI think the presentation of Theorem 1 and its connection to spectral augmentations could be improved. It would be useful to provide an intuition for how $\\epsilon$ and $\\epsilon'$ depend (asymptotically) on the model and augmentation hyperparameters ($k,\\delta,\\dots$). While information about this is provided in formal detail in the Appendix, I think the presentation in the main section could at least provide a general idea of how the upper and lower bounds are actually related to these hyperparameters. The motivation for this theorem and how it is connected to spectral augmentations is also somewhat vague. It is not fully clear to me why the fact that the InfoNCE loss is constrained to a particular band of values has significant implications for whether or not spectral augmentations are useful. As far as I understand, graph augmentation methods (spectral or otherwise) are generally not motivated by the specific value that a contrastive loss reaches during training but by the graph perturbations that the embeddings are meant to be resilient to. While the empirical study shows that spectral perturbations seem to not be significantly better than simpler choices, I currently find it unclear how this theorem relates to those observations. Finally, it would be interesting to compare the range of the InfoNCE loss predicted by this theorem to the loss actually observed during training on a real dataset with given hyperparameters.\n\nThroughout the paper, there are also a few grammatical mistakes / strange phrasing choices that could be improved, such as:\n* \"Can GNN encoders learn spectral information from augmented graphs produced edge perturbations\" (Page 9, **by** edge perturbations?)\n* \"Are spectrum in spectral augmentation necessary?\" (Page 9)\n* ...a bunch of benchmarks...\" (Page 5, informal)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper examines the necessity and effectiveness of spectral augmentation in the context of contrastive graph self-supervised learning (CG-SSL). It is shown that shallow GNNs consistently outperform deeper ones in CG-SSL, and theoretical bounds on the InfoNCE loss are provided. It is further demonstrated empirically that simple edge perturbations match and sometimes surpass the performance of spectral augmentation methods while being computationally more efficient. Ablation experiments and a statistical analysis support the conclusion that spectral information is not a key factor in the success of edge perturbation methods, advocating for simpler, more efficient augmentation strategies in CG-SSL.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* Clarify the presentation of Theorem 1 and its relationship to spectral augmentations\n* Potentially add an experimental comparison of the InfoNCE bound from Theorem 1 and the actual loss values during training\n* Fix grammar/spelling issues", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "tV9f3huYXb", "reviewer": "Reviewer_j2VY", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The research question in challenging and helpful, demonstrating that pure edge permutations are enough for GCL. This could pave the path for future research directions.\n2. The manuscript is well-structured, with clear sections that logically lead the reader through the research process and findings.\n3. The theoretical analysis complements the empirical results, offering a more complete understanding of the phenomena observed.\n4. The use of multiple baselines and datasets adds robustness to the findings.\n\nWeaknesses and questions:\n1. In section 4, authors only use SPAN as spectral augmentation to show the limitations of shallow GNNs while there are many other alternatives. Also, authors only proved that the expressiveness of shallow GNNs using InfoNCE loss are bounded while there are other loss functions as authors mentioned.\n2. In figure 1, authors show that the shallow GNNs (1 or 2 layers) usually have better performances than deeper ones. However, in theorem 1, authors claim that sophisticated spectral augmentations may not significantly outperform simple ones in shallow architectures and potential benefits of coupling spectral augmentations with deeper GNN architectures remain an open question. So when increasing the layers, how would the theorem support the experimental findings? If the loss is not bounded strictly like this, why would the performance drop drastically?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This manuscript presents a critical evaluation of the role of spectral augmentation in Contrast-based Graph Self-Supervised Learning. The authors challenge the prevailing belief in the importance of spectral properties for learning performance and propose that simple edge perturbations can achieve comparable or superior results with greater computational efficiency.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the weaknesses part, and discuss the potential solutions to the questions.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "XgvWMYLgME", "reviewer": "Reviewer_5WMb", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strength**\n\nThe paper is well-written and performs multiple experiments on graph and node representation learning datasets. The paper lists the necessary background and details needed to understand the contribution of the paper. It studies whether spectral augmentations[1] are really necessary. The paper identifies the computational cost of using spectral augmentation while performing similarly or lower than adding/dropping edge techniques. \n\n**Weakness**\n\nEven if the paper is well written, the main weakness of the paper is that it doesn't propose any new method. Future research can use it to avoid spectral augmentation, but they could reach this conclusion if they tried a few other augmentation techniques. \n\nThe paper shows a theoretical analysis of InfoNCE bounds on Theorem 1. Even though it might be important to show the bounds of the loss, I don't find it convincing enough to show how that is a downside for spectral augmentation. The numerical estimation also gives an estimated number, but it's not stated how that would compare to edge perturbation augmentations. Knowing there is a bound doesn't necessarily mean it's performing worse unless there is a way to compare it with another estimated bound. \n\nThe paper doesn't compare the preferred edge perturbation technique with other augmentation techniques. For example, how good is it compared to node feature augmentation methods [2]? Even though the paper focuses on topological augmentation, it would be great to see the result.\n\n\n**References**\n\n[1] \tNian Liu, Xiao Wang, Deyu Bo, Chuan Shi, Jian Pei: Revisiting Graph Contrastive Learning from the Perspective of Graph Spectrum. NeurIPS 2022\n\n[2] A Zhao, Tong; Jin, Wei; Liu, Yozen; Wang, Yingheng; Liu, Gang; Graph Data Augmentation for Graph Machine Learning: A Survey, arXiv e-prints, Art. no. arXiv:2202.08871, 2022. doi:10.48550/arXiv.2202.08871.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper critiques the importance of spectral augmentation in training contrastive models for learning representations of graphs in a self-supervised way. The authors argue that a simple edge perturbation is more effective than spectral augmentation for generating different views of data while at the same time being more computationally efficient. They perform extensive experiments on multiple node and graph classification datasets to prove their point.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I would like to see at least one case study (it can be in the appendix) discussing how the edge perturbation augmentation method compares to node feature augmentation techniques.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents a well-executed empirical and theoretical analysis that challenges the necessity of spectral augmentations in contrast-based graph self-supervised learning, demonstrating that simple edge perturbations achieve comparable or superior performance with lower computational costs. While the connection between theoretical and empirical findings could be further refined, the authors have sufficiently addressed reviewer concerns through additional experiments and clarifications, making this a strong contribution to the field. I recommend acceptance with minor revisions, contingent on the authors incorporating the revisions outlined in their rebuttal.
Decision: Accept (poster)