Self-supervised Masked Graph Autoencoder via Structure-aware Curriculum
Authors: Haoyang Li
Xin Wang
Zeyang Zhang
Zongyuan Wu
Linxin Xiao
Wenwu Zhu
Venue: ICML 2025 spotlightposter (2025)
Keywords: Curriculum Learning
Primary area: general_machine_learning->representation_learning

Abstract: Self-supervised learning (SSL) on graph-structured data has attracted considerable attention recently. Masked graph autoencoder, as one promising generative graph SSL approach that aims to recover masked parts of the input graph data, has shown great success in various downstream graph tasks. However, existing masked graph autoencoders fail to consider the degree of difficulty of recovering the masked edges that often have different impacts on the model performance, resulting in suboptimal node representations. To tackle this challenge, in this paper, we propose a novel curriculum based self-supervised masked graph autoencoder that is able to capture and leverage the underlying degree of difficulty of data dependencies hidden in edges, and design better mask-reconstruction pretext tasks for learning informative node representations. Specifically, we first design a difficulty measurer to identify the underlying structural degree of difficulty of edges during the masking step. Then, we adopt a self-paced scheduler to determine the order of masking edges, which encourages the graph encoder to learn from easy to difficult parts. Finally, the masked edges are gradually incorporated into the reconstruction pretext task, leading to high-quality node representations. Experiments on several real-world node classification and link prediction datasets demonstrate the superiority of our proposed method over state-of-the-art graph self-supervised learning baselines. This work is the first study of curriculum strategy for masked graph autoencoders, to the best of our knowledge.

Self-supervised Masked Graph Autoencoder via Structure-aware Curriculum
Haoyang Li
Xin Wang'
Zeyang Zhang'
Zongyuan Wu!
Linxin Xiao
Wenwu Zhu
Abstract
1. Introduction
Graph-structured data is ubiquitous across various do- mains, including social networks, citation networks, and e-commerce systems. Graph neural networks (GNNs) have demonstrated significant success in learning meaningful rep- resentations from such data, particularly in supervised (Xu et al., 2019) and semi- (Kipf & Welling, 2017; Hamilton et al., 2017) learning settings, where task-specific labels are available to guide the learning process. However, acquiring a large amount of high-quality annotations often expensive and impractical in real-world applications.
Self-supervised learning (SSL) on graph- structured data has attracted considerable attention recently. Masked graph autoencoder, as one promising generative graph SSL approach that aims to recover masked parts of the input graph data, has shown great success in various downstream graph tasks. However, existing masked graph autoencoders fail to consider the degree of difficulty of recovering the masked edges that often have different impacts on the model performance, resulting suboptimal node representations. To tackle this challenge, in this paper, we propose a novel curriculum based self-supervised masked graph autoencoder that is able to capture and leverage the underlying degree of difficulty of data dependencies hidden in edges, and design better mask recnstrconntt pretext tasks for learning informative node representations. Specifically, we first design difficulty measurer to identify the underlying structural degree of difficulty of edges during the masking step. Then, we adopt self-paced scheduler to determine the order of masking edges, which encourages the graph encoder to learn from easy difficult parts. Finally, the masked edges gradually incorporated into the reconstruction pretext task, leading to high-quality node representations. Experiments on several real-world node classification and link prediction datasets demonstrate the superiority of our proposed method over state-of-the-art graph sufervupeee learning baselines. This work the first study of curriculum strategy for masked graph autoencoders, the best of our knowledge.
Self-supe learning (SSL), an unsupervised paradigm widely adopted in computer vision and natural language processing (Chen et al., 2020; He et al., 2020), has re- cently gained significant attention in the field of graph learn- ing. SSL. enables models learn informative representa- tions by solving carefully designed pretext tasks without requiring labeled data. Existing graph SSL methods can be broadly categorized into contrastive and generative ap- proaches. Contrastive methods, such as DGI (Veličković et al., 2019), MVGRL (Hassani & Khasahmadi, 2020), and BGRL (Thakoor et al., 2022), predominate the field by lever- aging instance discrimination as the primary pretext task. Although augmentation-
variants like AFGRL (Wang et al., 2022a) and IGCL (Li al., 2023a) present promis- ing alternatives, many classical contrastive methods still depend heavily on heuristic graph augmentations. Their per- formance can degrade when the selected augmentations are misaligned with the objectives of downstream tasks (Zhang et al., 2021a). In contrast, generative SSL methods address this limitation more naturally by reconstructing missing components of the input graph. Representative models such GPT-GNN (Hu et al., 2020b). GraphMAE (Hou al., 2022), and S2GAE (Tan et al., 2023) demonstrate strong performance while avoiding the need for manually crafted augmentations.
Despite the notable progress of generative graph SSL meth- ods, existing approaches typically ignore the varying dif- ficulty levels of pretext tasks during training and treat all training samples uniformly, resulting in suboptimal perfor- mance. Intuitively, pretext tasks should be designed to start with easier data samples and gradually progress to more dif- ficult ones. Introducing overly challenging tasks at the early
'Dppartment of Computer Science and Technology. BN- Rist, Tsinghua University, Beijing. China. Correspondence Wenwu Zhu
to: Xin Wang <xin_ <xii..ang@ttsiiiiie.... wang@@singhua..du... <wwzhu wwwrhh@tsinghua.cdd.ro
Proceedings of the 4dnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Self-supervised Masked Graph Autoencoder via Structure-aware Curriculum
stages of training can overwhelm the GNN encoder, which is typically initialized with random parameters and lacks the capacity to handle complex reconstructions. Conversely, prolonged training on overly simplistic tasks yields dimin- ishing benefits and fails to further improve representation quality. The design of tailored easy-to-hard pretext tasks for enhancing graph representation learning remains an under- explored direction, which poses the following challenges.
model can achieve significant performance gains against ofate-of-the-art methods.
The contributions of this paper are summarized as follows:
We introduce a novel method that trains the GNN en- coder by presenting data in a tailored, easy-to-hard order, enabling more effective design of pretext tasks, To the best of our knowledge, this is the first work to explore curriculum learning in graph self-supervised learning.
It is technically difficult to design tailored reconstruc- tion tasks to encourage the GNNs to capture informa- tive patterns of the input graph into representations.
We propose a unified framework that jointly recon- structs missing edges based on the unmasked graph structure and schedules training edges using a self- paced learning strategy, thereby improving the effec- tiveness of the GNN encoder.
It is challenging to derive a proper principle to quantify the difficulty of reconstruction samples for training the GNNs.
It is also non-trivial to design a feasible scheduling strategy to gradually exploit data samples for recon- struction by explicitly considering the current training status of GNNs.
We provide theoretical analysis of the convergence properties of the proposed Cur-MGAE method and demonstrate through extensive experiments that it con- sistently outperforms state-of-the-ar graph SSL meth- ods, including both contrastive and generative ap- proaches.
To tackle these challenges, we propose Curriculum Masked Graph AutoEncoder (Cur-MGAE), a novel framework de- signed to capture and leverage the inherent difficulty of struc- tural dependencies in graph edges. Cur-MGAE aims to construct more effective mask-reconssrructinn pretext tasks by integrating a curriculum learning paradigm into genera- tive graph self-supervised learning. Specifically, our method enables GNNs to learn informative representations by gradu- ally incorporating training samples in a tailored easy-to-hand order. We first design a seuuucuur-waare edge reconstruction task, where the goal is to recover intentionally masked edges based on the remaining unmasked graph structure. This pre- text task encourages the GNN encoder extract mcaningful patterns from the graph. To quantify task difficulty, we intro- duce a self-supervised mechanism that identifies the easiest K edges the encoder is most confident in reconstructing. This allows for a principled estimation of reconstruction difficulty across edge samples. Furthermore, we develop a self-paced learning strategy that dynamically selects edges to be used in training. progressively increasing the task dif- ficulty in alignment with the encoder's evolving learning capacity. The processes of edge selection and structural re- construction are integrated into a unified training framework. Ultimately, the GNN encoder is trained using a meaningful curriculum that aligns edge difficulty with model capacity, yielding more powerful node representations and improved performance on downstream tasks.
The rest of the paper is organized as follows. We first introduce the details of our proposed Cur-MGAE method in Section 2. In Section 3, we present the experimental results to show the effectiveness of the method, including quantitative comparisons, ablation studies, etc. We review the related works in Section 4. Finally, we conclude this work in Section 5.
2. Method
In this section, we present Cur-MGAE, self-supervised framework designed to learn informative representations through the structure-aware curriculum. Specifically, Cur- MGAE consists of three key components: a structure-aware masked autoencoder, a complexity-gu -uided curriculum mask- ing module, and a self-paced mask scheduler. The overall framework is illustrated in Figure 1. The key notations in the method are summarized in Appendix A.
2.1. Structure-aware Masked Autoencoder
We propose a structure-aware masked autoencoder based the edge reconstruction task to learn informative node representations without requiring extra supervision.
GNN Encoder. Let the input graph be denoted as G = (V, E), where V and È are the sets of nodes and edges, respectively. can be represented as G = (X, A), where X is the node feature matrix and A is the adjacency matrix. We apply GNN to encode node representations:
We theoretically analyze the convergence guarantee of this tailored training paradigm by demonstrating its ability to avoid saddle points and achieve second-order convergence. Extensive experiments on various real-world node classifica- tion and link prediction benchmarks show that our proposed
(A) COM(N (t-1), AGGG( (k-1) :ue E No)),
(1)
2

---

Self-supervised Masked Graph Autoencoder via Structure-aware Curriculum
Self-paced Mask Scheduler
Complexity-guidee Curriculum Masking
① Difficulty-based Edge Selection
Scheduler
Easy
Hard
(Ages)
mask ratio upper-bound
ratio
0.8
encoder
0.6 sorted
decoder
Masked Edge
0.9
2 Random-baste banndd Edge Selection
(Amss Agux + Agus)
0.7
Input Graph
Residual Graph
Curriculum Edge (A(9)
(A)
(R
Ap
Reconstruction
Aues)
[Aazs]
Loss
Structure-aware Masked Autoencoder
Predict
Reconstructed Graph
Input
(A,c)
Cross-correlation decoder
Layer
First Layer
A Agastt
Figure 1. The framework of our proposed Cur-MGAE method. Given input graph, first introduce campplexity-guidee. curriculum masking module identify edges masked, where each edge is assigned a difficulty score on reconstruction residual error. Next, we design oif-paced mask scheduler dynamically schedule the masking curriculum according the training stage. Finally, we employ structure-awes aware masked autocncoder to perform self-supervised reconstruction of the graph structure.
where 5. is the embedding of node at the k-th layer, and N. = {u (v, u) E }} denotes its neighborhood. AGG(-) aggregates messages from neighbors, and COM(-) com- bines them to update embedding. We stack K GNN lay- ers to derive multi-hop embeddings (h (1) 11 ,,.",...,h
structural patterns. The resulting edge embeddings are fed into a multilayer perceptron (MIP) with a sigmoid acti- vation to estimate the existence probability each edge: g(u, u) MLP(he...). By selectively preserving informa- tive and correlated features, this design filters noise and facilitates more accurate and efficient edge prediction.
h (K)
The final node representations are denoted as ENC(X, Nxd, where N is the number of nodes, d is the embedding dimension, and ENC(.) the encoder.
Reconstruction Task. We adopt maak-reecnstruuctio paradigm for self-supervised learning to enhance the quality of the learned node representations. Specifically, we select a part of the edges be masked the original graph to obtain the perturbed graph: Á A Amask We denote Amask the adjacency matrix of the masked edges Enusk. Then adopt the reconstruction loss as the supervision signal: LSst. {(A, DEC(ENC(, A)), whose implementation is as follows:
Cross-correlation Decoder. After obtaining node embed- dings from the GNN encoder, design cross cross-correlation decoder reconstruct the graph structure by capturing inher- ent similarities between nodes following (Tan et al., 2023). Specifically, we compute edge embeddings as:
heg 1 k.
where C denotes element-wiss multiplication, represents concatenation, and hee... E k&dk? is the resulting edge embedding. This formulation emphasizes shared features between node pairs while suppressing dissimilar compo- nents, enabling the model retain only highly correlated
log exp(g(v, u))
LSSL
(3)
|Emask
Ever exp(g(v, +())
(v.u)e
g(-) is the predicted probability of the presence of an ex- isting edge, namely g(v, u) ML.P(I 11 1.)))
3

---

Self-supervised Masked Graph Autoencoder via Structure-aware Curriculum
where 1 and h denote the j-th and k-th hidden repre- sentation of node u and v, respectively, The learned node representations encode rich structural and attribute infor- mation, sufficient to reconstruct the original graph from perturbed inputs and further enhance performance in down- stream tasks.
K during training is non-trivial. Edge selection inherently poses discrete optimization problem over a large topologi- cal space, which significantly complicates the learning pro- cess. To address this, we relax the edge selection matrix (t)) from binary values to continuous values within [o, 1], trans- forming the problem into a continuous constrained optimiza- tion task. Specifically. we treat the masking constraint as a Lagrangian multiplier and introduce a regularization compo- nent to the loss function: S(S; X, A) = 2||S(() @ A All- Here, S denotes the soft edge selection matrix at training iteration I, sharing the same dimensions as the adjacency matrix A. After optimization, the entries in ((t) are thresh- olded at 0.5 to yield a binary mask 0, 1 for edge selection, resulting in the masked adjacency matrix A (1) = =(( @ A,
2.2. Complexity-guide Curriculum Masking
Since different edges in graph contribute unequally to its structure, randomly masking edges can pose optimization challenges during the reconstruction process. In particular, masking too many critical structural edges early in training may lead to excessively difficult reconstruction tasks, es- pecially when the GNN encoder is still undertrained. To mitigate this issue, we introduce complexity- guuded cur- riculum masking module that progressively increases task difficulty by selecting edges in an easy-to-hard manner. The key idea is to identify structurally important edges and post- pone their masking, thereby enabling a smoother and more effective learning trajectory.
where @ denotes element-wise multiplication.
Note that the regularization term promotes the masking of as many edges as possible, governed by the coefficient X. As À increases during training, more edges are gradually incorporated. This process effectively schedules edge mask- ing in an easy-to-hard manner. The evolving strategy for updating À is detailed in Appendix D.3. Combining both the residual-based selection and the regularization term (Zhang et al., 2023a), the loss function for our self-paced mask scheduler is given by:
Specifically, we identify edges that are structurally impor- tant to the graph and progressively mask them to increase the learning difficulty during the training process. We for- mally define the difficulty of an edge as a score reflect- ing how challenging it is for the current model to predict the edge correctly. To quantify this difficulty, we first use the current model to reconstruct the original graph as: A₁ DEC(ENC(X, A)).
+ LSPCI = B > & AS)
(4)
where 33 is balancing hyperparameter, S extracts the se- lected edges, and R.g = || - AW'1l denotes the edge residual, with A being the predicted edge value. The L2 norm is used for measuring residuals.
The reconstructed adjacency matrix Ar captures the model's 's internal estimation of edge probabilities, which can be interpreted as its confidence in the existence of each edge. Intuitively, lower confidence suggests that an edge harder to reconstruct for the current model, indicating higher structural complexity. We therefore propose use the structural residual (Zhang et al., 2023a) between the original and predicted graphs as a proxy for edge difficulty: R = A- A By applying a masking strategy that targets the K casiest edges, those with the smallest residuals, we simplify the reconstruction task, particularly during the early training stages. This allows the model to focus on learning fundamental structural patterns before encountering more complex ones (Zhang et al., 2023a; Li et al., 2023b). Conse- quently, this curriculum- guidedd masking strategy enhances both the efficiency and effectiveness of the training process.
However, continuously increasing the number of masked edges may eventually compel the model make uninformed or arbitrary predictions about the graph structure. To avoid this issue, we introduce mask ratio hyperparameter that constrains the maximum proportion of edges allowed to be masked. Another critical concern is that relying solely on difficulty-based edge selection tends to consistently mask only the easiest edges during training. This could limit the model's generalizability by overfitting these simpler struc- tures. To address this, we introduce split ratio hyperparam- eter that enables portion of the masked edges to be selected randomly. Specifically, a fraction of the masked edges, de- noted as ADES, is sampled uniformly at random, while the remaining edges, denoted as ARES, are selected based on their difficulty scores. The union of these two subsets forms the complete masked edge set Amask. A lower split ratio results in a higher degree of randomness in the masking pro- cess, thereby encouraging exploration. Conversely, a higher split ratio prioritizes difficulty-based masking, enhancing exploitation. By appropriately tuning this hyperparameter, we strike a balance between exploration and exploitation, thereby mitigating overfitting and improving the quality of
2.3. Self- Self-paced Mask Scheduler
Here, we propose a self-paced mask scheduler to progres- sively and autonomously incorporate an increasing num- ber of edges throughout the training process (Zhang et al., 2023a; Li et al., 2023b). One straightforward solution is to gradually increase the value K during the training process. However, dynamically identifying and updating suitable
4

---

Self-supervised Masked Graph Autoencoder via Structure-aware Curriculum
Algorithm 1 The optimization process of Cur-MGAE
which incurs a complexity of O(Ed+ Nd)). The decoder and the self-paced mask scheduler each contribute a time complexity of O as they involve computing residual errors for each edge. The complexity- -gidded curriculum masking module operates with a time complexity of O(F), since it selects from existing edges rather than the full x set of potential edges. Overall, the time complexity of our method is comparable to the baselines, which also typically scale (EE Nd?).
1: Input: Node features X, adjacency matrix A, step size 14
regularization coefficient 7
2: Output: Trained GNN parameters
3: Initialize w ( and X
4: Compute A A0) ( A
5: while not converged do
6: ((t)
Cest A (t-1): w) + lll
w((t-1||
7: Generate embodding ( from A using the updated GNN
model f
8: For all node pairs (i,j), predict edge existence Ag
2.5. Theoretical Analyses
g(2!"),,
We present theoretical analyses on the convergence proper- ties of our method in Theorems 1 and 2 following (Zhang et al., 2023a). Detailed proofs are provided in Appendix B.
9:
Relax ( to the continuous domain and optimize it as ((0) argmingCsspr + 2 S((
10:
X = [[(i.)): S 0.53|
11:
if K 2 mask ratio [E] then
Theorem 1 (Convergence Away from Saddle Points). For a sufficiently large ", if the second derivatives of CSSL AX,A(t w) and f(S; X, A) are continuous, any bounded sequence (w(t) ( generated by Algorithm I with random initialization will almost surely avoid conver- gence any strict saddle point of Call.
12:
K = mask ratio x |8]
13:
else
Update based on the designed curriculum pace end if
15:
16:
Select the top-split ratio x K edges with the highest Siy
values and assign to Si!)
17:
Randomly select the remaining (1 - sppit ratio) x K edges
Theorem 2 (Convergence to Second-order Stationary Points). For sufficiently large y, if the second deriva- tives of LSSL (X, A (t-1):w), and f(S; X, A) are continu- ous, and both functions satisfy the (KL) property (Wang et al., 2022b), then any bounded se- quence (wit), S()) generated by Algorithm with random initialization will almost surely converge to a second-order stationary point of Call.
and assign to RES
18:
( S(4) + RES
19:
Update the perturbed adjacency matrix A = =(()) @ A end while
20:
the learned node representations.
2.4. Optimization Procedure
3. Experiment
Our proposed model aims to minimize the objective func- tion Lall, which involves optimizing two distinct sets of parameters. This naturally leads to challenging bi-level optimization problem. To address this, we design an op- timization algorithm that jointly trains two separate self- supervised modules, each with its corresponding objective. The overall loss function is formulated as:
In this section, we conduct comprehensive experiments to evaluate the effectiveness of the proposed Cur-MGAE method. This includes the experimental setup. quantita- tive evaluations node classification and link prediction benchmarks, and in-depth analyses. Additional experimen- tal results are provided in Appendix G.
Lat LESt + LSPOL.
(5)
3.1. Experimental Setup
To ensure smooth transition across training iterations, we incorporate regularization terms into the optimization pro- cess: 3/l - ((( and S|[ - g(t-D)|. These terms penalize abrupt changes in the model parameters w and the edge selection matrix S, thereby stabilizing training dynamics. The complete training procedure is outlined in Algorithm 1.
Datasets. We evaluate node classification on three Plan- etoid datasets (Cora, Citeseer, and Pubmed (Sen et al., 2008)) and three commonly used citation/co-authorship datasets: Coauthor-CSS (Shchur et al., 2019), Coauthor- Physics (Shchur et al., 2019), and OGBN-arxiv (Hu et al., 2020a). Accuracy (%) is used as the evaluation metric for these tasks. For link prediction, we use the same three Plane- toid datasets and additional large-scale benchmarks from the Open Graph Benchmark (OGB) (Hu et al., 2021), including OGBN-ddi, OGBL-collab, and OGBL-ppa. We report the area under the ROC curve (AUC, %) (Bradley, 1997) for the three Planetoid datasets, and the Hit rate (Hits @NtssN) datasets, following (Tan et al., 2023) for fair comparison.
Time Complexity, The time complexity of our proposed model is O where N and E denote the numbers of nodes and edges in the graph, respectively, and is the dimensionality of the node representations. Specifically, our model adopts a message-passing GNN as the encoder,
N) for OGB
5

---

Self-supervised Masked Graph Autoencoder via Structure-aware Curriculum
Table 1. Node classification accuracy (%) of our proposed method and baselines. In each column, the boldfaced score denotes the hest result among all methods. The rightmost column shows the average rank, Our method achieves the best average rank.
Dataset
Cora
Citeseer
Pubmed
Coauthor-CS
Coauthor- Coauthor-Physics
OGBN-arxiv
Rank
DGI
85,41 + 0.34
74.51 0.51
76.80 0.60
92.77 : 0.38
94.55 : 0.13
67.08 0.43
9.50
GIC
87.70 # 0.01
76.39 # 0.02
77.40 # 1.90
91.33 0.30
93,49 0.42
64.00 0.22
9.17
MVGRL
85.86 + 0.15
73.18 0.22
80.10 0.70
92.87 = 0.13
95.35 0.08
68.33 0.32
8.42
BGRL
86.16 + 0.20
73.96 = 0.14
82.05 = 0.85
93.35 + 0.06
96.16 0.09
71.77 = 0.19
4.00
GAE
83,60 0.52
63.37 = 1.21
78.23 1.63
89.79 0.09
93.26 0.05
66.01 #
13,67
GraphSage
74.30 + 1.84
89.74 81.9 2.15
9.06
64.79
13.00
ARGVA
85.86
81.51 1.00 0.86
84.68
0..1
1..06
12.08
GPT-GNN
84.69 + 0.09
81.45 0.13
91.07
0.15
70.16
10.33
RRL
0.13
59.57
75,06
0.95
0.02
66.36
14.33
GraphMAE
72.48 0.40
81.10
93.47 0.04
9..13
7..86
6.50
GraphMAE2
0.60
0.30
0.50
9.11
9,,44
7.08
8.25
MaskGAE
0.05
0.07
0.45
9.05
9..79
7..1
4,50
Bandana
73.60 # 0.16
93.10 0355
9.057
7.209
6.33
AUG-MAE
84.30 0.40
73.20 = 0.40
81.40
92.15
0.63
71.90
8.58
S2GAE
86.15
74.60
= 0.06
8.21
91.70 0.08
9.00
7.002
4.50
Cur-MGAE
87.25 0.55
74.68 = 0.37
85.86
92.69 +
95.91 = 0.05
73.00
0.06
2.83
Baselines. We compare Cur-MGAE againss two groups of otate-of-the-arr baselines. The first group in- cludes contrastive graph self-supervised learning meth- ods: DGI (Veličković et al., 2019), GIC (Mavromatis & Karypis, 2021), MVGRL (Hassani & Khasahmadi, 2020),
reconstruction-bassee pretext tasks that recover masked struc- tures from the remaining graph context. Our curriculum- based method Cur-MGAF achieves the best performance on 2 out datasets and reports competitive results on the remaining datasets. For example, it improves performance by approximately 2% over the strongest baselines on OGBL- ddi and OGBL-ppa. This improvement is attributed to Cur- MGAE 's ability to adaptively select training samples based on task difficulty, unlike most baselines that treat all training data equally, leading to suboptimal results. MaskGAE (Li et al., 2023d), a strong baseline that jointly reconstructs masked edges and node degrees, performs well on smaller datasets but underperforms on large-scale benchmarks. A plausible explanation is that it overlooks the varying dif- ficulty of reconstructing different edges, which becomes more impactful in large, complex graphs where informative representations are harder to extract. In contrast, our method introduces a curriculum-dric -driven strategy that prioritizes cas- ier samples in early training stages and progressively incor- porates harder ones. Notably, none of the baselines achieves consistently strong performance across all datasets, whereas Cur-MGAE demonstrates stable and superior effectiveness.
and BGRL (Thakoor et al.. 2022). The second group in- cludes generative graph SSL methods such as GAE (Kipf
& Welling, 2016), GraphSAGE (Hamilton et al., 2017),
ARGVA (Pan et al., 2019). GPT-GNN (Hu et al., 2020b),
RRL. (Zhu et al., 2020), GraphMAE (Hou et al., 2022),
GraphMAE2 (Hou et al., 2023), MaskGAE et al., 2023d),
Bandana (Zhao al., 2024), AUG-MAB (Wang et al., 2024),
and S2GAE (Tan al., 2023).
3.2. Experimental Results
Node Classification. Table summarizes the node clas- sification accuracy of Cur-MGAE and all basclines. Our method outperforms both contrastive and generative self- supervised baselines, achieving the highest average rank. This result demonstrates the benefit of scheduling train- ing data using a difficulty-aware curriculum derived from reconstruction residuals, which enables more effective rep- resentation learning. For instance, Cur-MGAE improves classification accuracy by 1.67% on Pubmed and nearly 1% on OGBN-arxiv compared to the strongest baseline.
3.3. Visualization of Learned Edge Selection Curriculum
To qualitatively evaluate the learned edge selection strat- egy, we construct synthetic datasets with ground-truth edge difficulty labels, following previous works (Karimi et al., 2018; Abu-El-Haija et al., 2019; Zhang et al., 2023a). Each synthetic graph consists of 5,000 nodes partitioned into 10 equally sized groups, with node labels ranging from to 10. The corresponding visualization is provided in Appendix F, The node features are generated from overlapping multi- Gaussian distributions that define each node's 's position in
Link Prediction. Table presents the link prediction performance of Cur-MGAE and baseline methods!. The results indicate that generative graph SSL methods (c.g., GraphMAE, MaskGAF, S2GAE) generally outperform contrastive methods, highlighting the effectiveness of the
NNoe that GraphMAF2 and AUG-MAE are omitted here since they are node graph classification methods and designed for link prediction tasks.
6

---

Self-supervised Masked Graph Autoencoder via Structure-aware Curriculum
Table Link prediction results (%) of our proposed method and baselines. Cur-MGAE achieves consistently strong performance across both small-scor scale and laage-scale benchmark datasets. "_" indicates out-of-memory errors on a 24GB GPU, while "Y" denotes that the method is not applicable to the corresponding dataset.
Dataset
Cora
Citeseer AUC
Pubmed AUC
OGBL-ddi Hits@20
OGBL-coolaab 5o
OGBL-ppa Hits@ 10
Rank
Metric
AUC
DGI
90.02 # 0.80
95.53 + 0,40
91.24 + 0.60
11.17
GIC
93.54 #: 0.60
97.04 + 0.50
93.71 = 0.30
9.67
MVGRL
87.46 0.38
88.95 0.66
88.36 + 0.59
13.33
BGRL
87.08 = 0.24
85.82 0.36
96.75 0.12
21.58 1.92
12.17
GAE
91.09 1 0.01
90.52
96,40
37.07 5.07
44.75 # 1.07
0.44
7.33
GraphSage
86.33 1.06
85.65
53.90 0.87
4.74
54.63 1.12
1.87 0.67
9.00
ARGVA
92.40
0.00
0.000
4.66
28.3
0.26
7.83
GPT-GNN
9
91.36 0.66
5.96 0..83
42.41
1.57
6.67
RRL
88.46 1.85
85.47 1.01
9..1
16.84
2.99
0.24
10.83
GraphMAE
89.19 0.00
91.20
93.72
1.62
0.28
10.92
MaskGAE
96.66 0.17
=
0.04
16.25 - 1.60
3259
0.20
5,00
Bandana
0.12
97.26 9.21
48.67
1.26
4.92
S2GAE-SAGE
95.05 0.76
94.85
97.38
66.00
49.27
1.37 0.38
4.67
S2GAB-GCN
93.52 # 0.23
93.29
98.30 # 0.12
65.91 + 3.50
54.74 # 1.06
3.98 + 1.33
3.83
Cur-MGAE
95.22 0.54
9..20
98.43 + 0.06
68.50 5.06
52.28 1.35
5.96 + 0.96
2.67
the feature space. The labels are then assigned according to the feature distributions, resulting in 10 distinct classes. Edge difficulty is defined based on the label similarity be- tween node pairs: edges between nodes with identical labels are considered easy, those between adjacent labels are of medium difficulty, and those connecting nodes with distant labels are deemed hard to reconstruct. To control the preva- lence of easy edges, we introduce a homophity coefficient (homo) that specifies the ratio of easy edges in the graph. For all other potential edges, the connection probability decreases exponentially with label distance. Formally, the probability of an edge between nodes u and v is defined as: Puc x e -ele-ool, where Ic,, col denotes the shortest label distance in a circular label arrangement. We generate three synthetic datasets by setting the homophily coefficient to O.I, 0.5, 0.9, and split each graph into training, validation, and test sets with equal numbers of nodes.
model becomes more expressive, it begins to select increas- ingly difficult edges, effectively expanding its learning scope in a controlled, progressive manner. Interestingly, the ho- mophily coefficient influences the dynamies of the easy-to- hard transition. As illustrated in the stacked plots, where the blue, orange, and red regions represent the relative pro- portions of selected easy, medium, and hard edges at each epoch, low homophily leads to a more aggressive curricu- lum. In this setting, the model selects substantial fraction of medium and hard edges even in the early stages of train- ing. In contrast, under high homophily, early edge selection is dominated by easy edges, with medium and hard edges incorporated more gradually. This pattern suggests that in highly homophilous graphs, the model adopts a more con- servative learning trajectory, initially relying on structurally similar (and easier) edges before progressively transition- ing to more challenging ones. These visualizations confirm that our structure-aware masking curriculum behaves as ex- pected, progressively selecting edges from easier to harder throughout the training process.
Learned Edge Selection Curriculum. Using the syn- thetic datasets described above, we visualize and compare the learned edge selection curriculum with the ground-truth edge difficulty distribution. Figure 2 shows the proportion of selected edges categorized as easy, medium, and hard throughout training. In this figure, each row corresponds to a different homophily coefficient, while each column represents a different split ratio, a hyperparameter that con- trols the trade-off between exploration and exploitation in edge selection. Across all settings, we observe a consistent trend: the model initially favors selecting easier edges and gradually incorporates harder ones as training progresses. This behavior is consistent with the intended design of our curriculum-drive training strategy. Specifically, in early epochs, the model focuses on easier edges that align with its current learning capacity. As training advances and the
3.4. Ablation Studies
To evaluate the effectiveness of our key modules and designs, we conduct ablation studies by modifying the components of Cur-MGAE. For simplicity, we present results on Cora, Citeseer, OGBL-ddi, and Coauthor-CS in Table 3, with similar trends observed on the remaining datasets. We use AUC (%) for link prediction and accuracy (%) for node classification as evaluation metries.
Variant 'w/o Curri.' It disables the complexity-guider curriculum masking module (Section 2.2) and instead ap- plies random masking. The performance drop demonstrates
7

---

Self-supervised Masked Graph Autoencoder via Structure-aware Curriculum
homo=0.1 split ratio=D.1
homo=0.1 split ratio=D.5
homo=0.1 split ratio=
Proporton sellactedd adges
1.0
easy
Proportion offellcted edges
easy
easy
medium hard
hard
Proportion ofa.llltedd
hard
04
0.2
02
02
0.0
0.0
0.0
25
20
Epochs
Epochs
Epocns
homo=0.5 0.5 split ratio=D.1
homo=0.5 5. split ratio=D.5
homo=0.5 split ratio=D.9
Proporton of selected adgos
easy
Proportion seleeted adges
essy
easy
medium
medium
0.
medium
hard
Proportion selecied
hand
2.6
0.6
6.
04
04
0.2
0.2
02
Epochs
Epochs
Epochs
homo=0.9 0.9 split ratio=D.1
homo= 0.9 splil ratio=D.5
homo=0.5 .99 split ratio=D.9
Proportonn of selected edgas
Proportion of swllcctdd edges
0.8
2.8
0.8
sellectdd
0.5
0.6
0.6
0.4
8.4
2.
essy
easy
0.2
medium
0.2
hard
hard
hard
Epochs
Epochs
Epocns
Figure 2. Edge selection dynamics across synthetic datasets under varying homophily coefficients (rows) and split ratios (columns). At each epoch, the stacked colored areas represent the relative proportions of selected easy (blue), medium (orange), and hard (red) edges.
that treating all samples equally during training can be sub- optimal. This supports the benefit of our structure-aware curriculum design in promoting better performance.
Variant 'w/o CC Dec.". This variant evaluates the impact of our specially designed cross-correlation decoder in the structure-aware masked autoencoder (Section 2.1). We re- place with a simpler inner product decoder while keeping all other components unchanged. The significant drop in per- formance demonstrates that the cross- correlaton decoder, by capturing multi-granular shared features between con- nected nodes, facilitates more informative representation learning and improves reconstruction accuracy.
Variant 'split ratio is 0". Setting the split ratio 0 means that the self-paced mask scheduler (Section 2.3) randomly selects fixed number of edges without considering their difficulty scores. Although this introduces stochasticity and helps prevent overfitting, the lack of difficulty-aware edge selection leads to noticeable performance degradation, highlighting the importance of mcaningful edge scheduling.
Variant 'w/o CC Dec. & Curri', In this variant, both the decoder and the curriculum masking are removed: we use inner product decoder and randomly mask the training samples. This combination results in the worst performance across all settings, confirming that the two modules, i.e., decoder and curriculum, play synergistic and crucial roles in achieving strong representation learning.
Variant 'split ratio is 1'. In this variant, we set the split ratio 1, which removes the randomness in the edge selec- tion process of the self-paced mask scheduler (Section 2.3). Together with the previous variant, these two variants aim to assess the effectiveness of the self-paced scheduling mech- anism. Without randomness, the scheduler consistently selects edges with the smallest difficulty scores during early training stages. This deterministic behavior may lead to overfitting and limit the model's ability to generalize, re- flected in the performance drop compared to the full model.
Overall, these ablation studies confirm the importance of the key components in our proposed method. The tai- lored structure-aware curriculum enables the identification of more informative edges by leveraging difficulty scores,
8

---

Self-supervised Masked Graph Autoencoder via Structure-aware Curriculum
Table 3. Ablation studies on key components. "Curri." refers the complexity-guidee curriculum masking module, and "CC Dee."
denotes the cross-correlatio decoder.
Link Prediction Citeseer
Node Classification Citeseer
Datasets
Cora
OGBL-ddi
Cora
Coauthor-CS CS
Cur-MGAE
95.22 0.54
95.20 + 0,31
68.50 + 5.06
87.25 + 0.55
74.68 a 0.37
92.69 = 0.17
w/o Curri.
92.89 0.40
93.66 + 0.23
61.70 9.66
86.08 4 0.15
73.92
91.67 = 0.03
split ratio split ratio O
93.80 1:24
92.17 1.13
62.90 11.31
91.58 0..7 0.44
9..12
92.21 + 0.52
62.49 8.97
86.93 + 0.15
00.24
91.69 0.02
w/o CC Dec.
87.43
85.49 + 0.35
22.69 3.65
83.05 + 0.90
0.325
90.55 = 0.24
w/o CC Dec. Curri.
87.21 0.69
85.18 + 0.99
20.73 + 1.72
82.89 0.11
69.09
0.93
89.93
while the split ratio introduces a controlled level of stochas- ticity to avoid overfitting. Meanwhile, the cross-correlation decoder mitigates the representational limitations introduced by the masking process and significantly enhances the re- construction quality.
dational approach in this domain is the "Baby Step" algo- rithm (Spitkovsky et al.,. 2010), which controls both the com- plexity and order of training samples. This idea was later extended to the self- self-paced learning paradigm (Kumar et al., 2010), which selects training samples based on their loss values, allowing models to learn at their own pace. In addi- tion, several automatic CL frameworks have been proposed, including transfer teacher (Hacohen & Weinshall, 2019), re- inforcement learning- based curriculum teacher (Zhao et al., 2020), and others customized for different datasets, mod- els, and objectives (Sinha et al., 2020). CL has also been integrated into various domains such as disentangled recom- mendation systems (Chen et al., 2021; Wang et al., 2023), combinatorial optimization (Zhang et al., 2022c), neural architecture search (Zhou et al., 2022: Yao et al., 2024; Qin et al., 2023), and video grounding (Lan al., 2023). Several studies have extended CL to graph domains (Li et al., 2023b), such as GNN-CI. (Li et al., 2024b) and Cur- Graph (Wang et al., 2021b). A central component of CL methods is the mechanism to assess sample complexity and guide the training schedule by determining the order or relative importance of samples. However, most existing methods heavily rely on label supervision to train encoders and overlook self superviee settings where labels not available. More importantly, these methods typically treat training samples as independent instances, whereas our ap- proach addresses a more challenging structure-aware cur- riculum setting in which training samples are inherently interconnected and thus cannot be treated as independent.
4. Related Work
Graph Self-Supervised Learning. Graph self-supervised learning (SSL) techniques (Liu et al., 2022; You et al., 2020; Peng et al., 2020; Xu et al., 2021; Sun et al., 2023b; Li et al., 2022c; 2021b; 2024a) are typically categorized into contrastive and generative paradigms. Recently, con- trastive methods have gained significant attention. These approaches primarily focus on negative sampling strate- gies, such as corruption-based negative pair construction in DGI (Veličković et al., 2019), and in-batch negatives used in GCA (Zhu et al., 2021). In contrastive learning, graph augmentation plays a critical role in creating effective train- ing signals. However, the theoretical understanding of graph augmentation remains limited, raising concerns about its label invariance and optimality. In contrast, generative SSL methods aim to reconstruct missing parts of input graphs and are generally divided into autoregressive and autoen- coding models. Although generative approaches have his- torically underperformed compared to contrastive methods, several notable autoregressive models have emerged, such as GPT-GNN (Hu et al., 2020b). In the autoencoding cate- gory, early models like GAE and VGAE (Kipf & Welling, 2016) set foundational benchmarks. More recent advances include GraphMAE (Hou et al., 2022), GraphMAF2 (Hou et al., 2023), GigaMAE (Shi et al., 2023), SeeGera (Li et al., 2023e), RARE (Tu et al., 2023), S2GAE (Tan et al., 2023), and Bandana (Zhao et al., 2024). Nonetheless, most existing methods neglect the varying difficulty levels of self- supervised tasks, treating all training samples equally and resulting in suboptimal performance on downstream tasks.
5. Conclusion
In this paper, we propose graph self-supervised learning strategy based on curriculum learning, named Cur-MGAE. which builds upon a masked graph autoencoder framework. Our method assesses the difficulty of reconstructing masked edges and thus guides the model to learn in an easy-to-har manner. This approach leads to the acquisition of more infor- mative graph representations. We provide a theoretical anal- ysis of the convergence properties of the proposed method. Extensive experiments on real-world benchmarks demon- strate that our proposed method consistently outperforms state-of-the-an graph self- self-supervised learning baselines in both node classification and link prediction tasks.
Curriculum Learning. Curriculum Learning (CL) is training strategy that starts with simpler tasks and gradually moves to more complex ones, inspired by the way humans learn in educational settings (Bengio et al., 2009; Wang et al., 2021a; Zhou et al., 2023; 2024; Huang et al., 2024; Zhang et al., 2024; Yao al., 2024; Ge et al., 2025). A foun-

---

Self-supervised Masked Graph Autoencoder via Structure-aware Curriculum
Acknowledgements
Fan, X., Gong, M., Wu, Y.,, Qin, A., and Xie, Y. Propagation enhanced neural message passing for graph representation learning. TKDE, 2021.
This work supported by National Natural Science Foun- dation of China No. 66.62222 Beijing National Research Center for Information Science and Technology under Grant No.BNR2023TD03006.
Feng, W., Li, H., Wang. X., Duan, X., Qian, Z.,, Liu, W., and Zhu, W. Multimedia cognition and evaluation in open environments. In Proceedings of the 1st Interna- tional Workshop on Multimedia Content Generation and Evaluation: New Methods and Practice, pp. 9-18, 2023.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which feel must be specifically highlighted here.
Gao, J., Gao, J., Ying, X., Lu, M., and Wang. J. Higher- order interaction goes neural: A substructure assembling graph attention network for graph classification. TKDE, 2021.
References
Ge, C., Wang, X.,, Zhang, Z., Chen, H., Fan, J., Huang, L., Xue, H., and Zhu, W. Dynamic mixture of curriculum lora experts for continual multimodal instruction tuning. In International Conference on Machine Learning, 2025.
Abu-El-Haija, S., Perozzi, B., Kapoor, A., Alipourfard, N., Lerman, K., Harutyunyan, H., Steeg, G. V., and Galstyan, A. Mixhop: Higher-order graph convolutional architec- tures via sparsified neighborhood mixing, 2019.
Gong, X., Yang, C., and Shi, C. Ma-gel: Model augmen- tation tricks for graph contrastive learning. Proceedings of the AAAI Conference on Artificial Intelligence, 37: 06 2023. doi: 10.1609/anai, v............255477
Bengio, Y., Louradour, J., Collobert, R., and Weston, Curriculum learning. In Proceedings of the 26th annual international conference on machine learning, pp. 41-48, 2009.
Hacohen, G. and Weinshall, D. On the power of curricu- lum learning in training deep networks. In International conference on machine learning, pp. 2535 3535-2544. PMLR, 2019.
Bradley, A. P. The use of the area under the roc curve in the evaluation of machine learning algorithms. Pattern recognition, 30(7):1 145- 1997.
Hamilton, W. L., Ying. R., and Leskovee, Inductive representation learning large graphs. NIPS' 17, pp. 1025-1035, Red Hook, NY, USA, 2017. Curran Asso- ciates Inc. ISBN 9781510860964.
Cai, J.. Wang, X., Li, H., Zhang, Z., and Zhu, W. Multi- modal graph neural architecture search under distribution shifts, In Proceedings of the AAAI Conference on Artifi- cial Intelligence, volume 38, pp. 1227-82333 2024.
Hassani, K. and Khasahmadi, A. H. Contrastive multi- view representation learning on graphs. In International conference on machine learning, pp. 4116-4126. PMLR, 2020.
Chen, H., Chen, Y., Wang, X., Xie, R., Wang, R., Xia, F., and Zhu, W. Currieulum disentangled recommendation with noisy multi-feedhack. Advances in Neural Informa- tion Processing Systems, 2116922--69366 2021.
He, K., Fan, H., Wu, Y., Xie, S., and Girshick, R. Mo- mentum contrast for unsupervised visual representation learning. Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 9729-9738. 2020.
Chen, H., Wang, X., Zhang, Z., Li, H., Feng, L., and Zhu, W. Autogfm: Automated graph foundation model with adaptive architecture customization. In International Con- ference Machine Learning, 2025.
Chen, T., Kornblith, S., Norouzi, M., and Hinton, G. A simple framework for contrastive learning of visual rep- resentations. In International conference on machine learning, pp. 1597-1607. PMLR, 2020.
Hou, Z., Liu, X., Cen, Y., Dong, Y., Yang, H., Wang, C., and Tang, J. Graphmae: Self-supervised masked graph autoencoders. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 594-604, 2022.
Ding, K., Wang, Y., Yang, Y., and Liu, H. Eliciting structural and semantic global knowledge in unsupervised graph contrastive learning. AAAT23MAАPΣ3EAANT 23/EAA233 AAAI Press, 2023. ISBN 978-1-57735 880-0. doi: 10.1609/
Hou, Z., He. Y., Cen, Y., Liu, X., Dong, Y., Kharlamov, E., and Tang, J. Graphmae2: A eeroddnngennanced masked self-supervised graph learner. In Proceedings of the ACM Web Conference 2023, WWW '23, pp. 737-746, 2023.
aaai. mai.vv37...2589.
10

---

Self-supervised Masked Graph Autoencoder via Structure-aware Curriculum
Hu, W., Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., Catasta, M., and Leskovec, J. Open graph benchmark: Datasets for machine learning on graphs. In NeurlPS, 2020a.
Li, H., Wang, X., Zhang. Z., Ma, J., Cui, P., and Zhu, W. Intention-awart sequential recommendation with struc- tured intent transition. IEEE Transactions on Knowledge and Data Engineering, (111)::540-54444 2021a.
Hu, W., Fey, M., Ren, H., Nakata, M., Dong, Y., and Leskovec, J. Ogb-Ise: A large-scale challenge for ma- chine learning on graphs, 2021.
Li, H., Wang, X., Zhang, Z., Yuan, Z., Li, H., and Zhu, W. Disentangled contrastive learning on graphs. Advances in Neural Information Processing Systems, 34, 2021b.
Hu, Z., Dong, Y., Wang, K., Chang, K.-W., and Sun, Y. Gpt- gnn: Generative pre-training of graph neural networks. In KDD, 2020b.
Li, H., Wang, X., Zhang, Z., and Zhu, W. Ood-gnn: -ffts--dist generalized graph neural network. IEEE Transactions on Knowledge and Data Engineer- ing, 2022a.
Huang, B., He, F., Wang, Q., Chen, H., Li, G., Feng, Z., Wang, X., and Zhu, W. Neighbor does matter: Curriculum global positive-negative sampling for vision- vision-language pre- training, In Proceedings of the 32nd ACM International Conference on Multimedia, pp. 8005-8014, 2024.
Li, H., Wang, X., Zhang, Z., and Zhu, W. Out-of-distribution generalization on graphs: A survey. arXiv preprint arXhv:2202.07887 2022b.
Ji, H., Wang, X., Shi, C., Wang, B., and Yu, P. Heteroge- neous graph propagation network. TKDE, 2021.
Li, H., Zhang, Z., Wang. X., and Zhu, W. Disentangled graph contrastive learning with independence promotion. IEEE Transactions on Knowledge and Data Engineering, 2022c.
Jiang, B., Kloster, K., Gleich, D. F., and Gribskov, M. Ap- trank: an adaptive pagerank model for protein function prediction on bi-relational graphs. Bioinformatics, 33 (12): 112):1829-883,, 2017.
Li, H., Zhang, Z., Wang, X., and Zhu, W. Learning invari- ant graph representations for ization. In Advances in Neural Information Processing Systems, 2022d.
general-
Jiang, W. and Luo, J. Graph neural network for traffic forecasting: A survey, arXiv preprint arXiv.2101.11174 2021.
Li, H., Cao, J., Zhu, J., Luo, Q., He, S., and Wang. X. Augmentation-free graph contrastive learning of invariant- discriminative representations. IEEE Transactions on Neural Networks and Learning Systems, pp. 1-11, 2023a. doi: N0.1109/TNLSS.2023.. 2023.32882.....
Karimi, F., Génois, M., Wagner, C., Singer, P., and Strohmaier, M. Homophily influences ranking of mi- norities in social networks. Scientific Reports, 8, 2018.
Kipf, N. and Welling, M. Variational graph encodes. In NeurlPS Workshop on Bayesian Deep Learning, 2016.
Li, H., Wang, X., and Zhu, W. Curriculum graph machine learning: A survey. International Joint Conference on Artificial Intelligence, 2023b.
Kipf, T. N. and Welling, M. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
Li, H., Zhang, Z., Wang, X., and Zhu, W. Invariant node representation learning under distribution shifts with mul- tiple latent environments. ACM Transactions on Informa- tion Systems, 42(1):1-30. 2023c.
Kumar, M., Packer, B., and Koller, D. Self- learning for latent variable models. Advances in neural informa- tion processing systems, 23, 2010.
Lan, X., Yuan, Y., Chen, H., Wang, X., Jie, Z., Ma, L., Wang, Z., and Zhu, W. Curriculum multi nelliineegttve augmentation for debiased video grounding. In Proceedings the AAAI Conference on Artificial Intelligence, 2023.
Li, H., Wang, X., Zhang, Z., Chen, H., Zhang, Z., and Zhu, W. Disentangled graph self-supervised learning for -attof-distribution generalization. In International Conference on Machine Learning, 2024a.
Lee, N., Lee, J., and Park, C. Augmentation-fiee free self- supervised learning on graphs. Proceedings of the AAAI Conference on Artificial Intelligence, 36:7372-7380, 06 2022. doi:
Li, H., Wang, X., Zhu, X., Wen, W., and Zhu, W. Dis- entangling invariant subgraph via variance contrastive estimation under distribution shifts. In International Con- ference on Machine Learning, 2025.
23677.20700.
Li, H., Cui, P., Zang, C., Zhang, T., Zhu, W., and Lin, Y. Fates of microscopic social ecosystems: Keep alive or dead? In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 668-676, 2019a.
Li, J., Wu, R., Sun, W., Chen, L., Tian, S., Zhu, L., Meng, C., Zheng, Z., and Wang, W. What's behind the mask: Under- standing masked graph modeling for graph autoencoders, 2023d.

---

Self-supervised Masked Graph Autoencoder via Structure-aware Curriculum
Li, Q.. Zhu, Z., and Tang, G. Alternating minimizations converge second-order optimal solutions. In Chaud- huri, K. and Salakhutdinov, R. (eds.), Proceedings of the 36th International Conference on Machine Learning, vol- ume 97 of Proceedings of Machine Learning Research, pp. 3935-3943, PMLR, 09-15 Jun 2019b.
Qin, Y., Wang. X., Zhang, Z., Chen, H., and Zhu, W. Multi- task graph neural architecture search with task-aware collaboration and curriculum. In Advances in Neural In- formation Processing Systems 36 (NeurIPS 2023), 2023.
Sen, P., Namata, G., Bilgic, M., Getoor, L., Gallagher, B., and Fliassi- Rad, T. Collective classification in network data. Al Magazine, 29(3):93-106, 2008.
Li, X., Ye, T., Shan, C., Li, D., and Gao, M. Seegera: Self- supervised semi-implicit graph variational auto-encoders with masking. Proceedings of the ACM Web Conference 2023, 2023e.
Shchur, O., Mumme, M., Bojchevski, A., and Günnemann, S. Pitfalls of graph neural network evaluation, 2019.
Li, X., Fan, Z., Huang, F., Hu, X., Deng, Y., Wang, L., and Zhao, X. Graph neural network with curriculum learning for imbalanced node classification, Neurocomputing, pp. 127229, 2024b.
Shi, Y., Dong, Y., Tan, Q.. Li, J., and Liu, N. Gigamae: Gen- eralizable graph masked autoencoder via collaborative latent space reconstruction. Proceedings of the 32nd ACM International Conference Information and Knowledge Management, 2023.
Liu, Y., Jin, M., Pan, S., Zhou, C., Zheng, Y., Xia, F., and Philip, S. Y. Graph self-supervised learning: A survey. IEEE Transactions on Knowledge and Data Engineering, 35(6):5879-599) 2022.
Sinha, S., Garg, A., and Larochelle, H. Curriculum by smoothing. Advances in Neural Information Processing Systems, 33:21653-21664 2020.
Ma, J., Cui, P., Kuang, K., Wang. X., and Zhu, W. Disen- tangled graph convolutional networks. In International conference on machine learning, pp. 4212-4221. PMLR, 2019.
Spitkovsky, V. I., Alshawi, H., and Jurafsky, D. From baby steps to leapfrog: How "less is more" in unsupervised de- pendency parsing. In Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, pp. 751-759, 2010.
Mavromatis, C. and Karypis, G. Graph infoclust: Maxi- mizing coarse-grain mutual information in graphs. In Pucific-Asia Conference on Knowledge Discovery and Data Mining, pp. 541-553. Springer, 2021.
Sun, D., Cao, M., Ding, Z.,, and Luo, B. Graph con- trastive learning with intrinsic augmentations. In Pan, L., Zhao, D., Li, L.,, and Lin, J. (eds.). Bio-Inspired Comput- ing: Theories and Applications, pp. 343-357, Singapore, 2023a. Springer Nature Singapore. ISBN 978-981-99 1549-1.
Miao, X., Zhang, W., Shao, Y.. Cui, B., Chen, L., Zhang, C., and Jiang, J. Lasagne: A multi-layer graph convolutional network framework via node-aware deep architecture. TKDE, 2021.
Sun, Q.. Zhang, W., and Lin, X. Progressive hard negative masking: From global uniformity to local tolerance. IEEE Transactions on Knowledge and Data Engineering, 35 (12):12932-12943, 2023b.
Mo. Y., Peng, L., Xu, J., Shi, X., and Zhu, X. Simple unsupervised graph representation learning. Proceedings of the AAAI Conference on Artificial Intelligence, 36(7): 7797-7805, Jun. 2022.
Tan, Q., Liu, N., Huang, X., Choi, S.-H., Li, L., Chen, R., and Hu. X. S2gae: Self-supervised graph autoencoders are generalizable learners with graph masking. In Pro- ceedings of the Sixteenth ACM International Conference on Web Search and Data Mining, pp. 787-795, 2023.
Pan, S., Hu, R., Long, G., Jiang, J., Yao, L., and Zhang, C. Adversarially regularized graph autoencoder for graph embedding, 2019.
Pan, S., Hu, R., Fung, S.-F., Long, G., Jiang, J., and Zhang, C. Learning graph embedding with adversarial training methods. In Proceedings of the International Conference on Learning Representations (ICLR 2020), 2020.
Thakoor, S., Tallec, C., Azar, M. G., Azabou, M., Dyer, E. L., Munos, R., Veličković, P., and Valko, M. Large- scale representation learning on graphs via bootstrapping. International Conference on Learning Representations, 2022.
Peng, Z., Huang, W., Luo, M., Zheng, Q., Rong, Y. Xu, T., and Huang. J. Graph representation learning via graphical mutual information maximization. In Proceedings of The Web Conference 2020, WWW '20, pp. 259-270, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 9781 450370233.
Tu, W., Liao, Q., Zhou, S., Peng, X., Ma, C., Liu, Z., Liu, X., Cai, Z., and He, K. Rare: Robust masked graph autoencoder. JEEE Transactions on Knowledge and Data Engineering, pp. 1-14, 2023.
12

---

Self-supervised Masked Graph Autoencoder via Structure-aware Curriculum
Veličković, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., and Bengio, Y. Graph attention networks. In ICLR, 2018.
Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks? In ICIRR 2019.
Yao, Y., Wang. X., Qin, Y., Zhang, Z.,, Zhu, W., and Mei, H. Data-augmented curriculum graph neural architecture search under distribution shifts. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 16433-16441, AAAI Press, 2024.
Veličković, P., Fedus, W., Hamilton, W. L., Liò, P., Bengio, Y., and Hjelm, R. D. Deep Graph Infomax. In Interna- tional Conference on Learning Representations, 2019.
Wang, H., Wang, J., Wang, J., Zhao, M., Zhang, W., Zhang, F. Xie, X., and Guo, M. Graphgan: Graph representation learning with generative adversarial nets. In Proceed- ings of the Thirty-Second AAAI Conference on Artificial Intelligence (AAAI 2018). pp. 2508 2015, 2018.
Ye, Y. and Ji, S. Sparse graph attention networks. TKDE, 2021.
You, Y., Chen, T., Sui, Y.. Chen, T., Wang, Z. and Shen, Y. Graph contrastive learning with augmentations. In NeurlPS, 2020.
Wang, H., Zhang. J., Zhu, Q. and Huang, W. Augmentation- free graph contrastive learning with performance guaran- tee, 2022a.
Yu, M., Ding, Z., Yu, J.. Zhang, W., Yang. M., and Zhao, M. Graph contrastive learning with adaptive augmentation for knowledge concept recommendation. In 2023 26th International Conference on Computer Supported Coop- erative Work in Design (CSCWD), pp. 1281-1286, 2023. doi: 10.
Wang, J., Li, H., and Zhao, L. Accelerated gradient-free neural network training by multi-convex alternating opti- mization, 2022b.
Wang, L., Tao, X., Liu, Q., Wu. S., and Wang. L. Rethink- ing graph masked autoencoders through alignment and uniformity, 2024.
10152806.
Zhang, H., Wu, Q., Yan, J., Wipf, D., and Yu, P. S. From canonical correlation analysis to self-super graph neural networks. Advances in Neural Information Pro- cessing Systems, 34:76-89, 2021a.
Wang, X., Chen, Y., and Zhu, W. A survey on curriculum learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(9):4555-435 4576, 2021a.
Zhang, M. and Chen, Y. Link prediction based on graph neural networks. In NeurIPS, pp. 5165-5175, 2018.
Wang, X., Pan, Z., Zhou, Y., Chen, H., Ge, C., and Zhu, W. Curriculum co oo-disentangled representation learning across multiple environments for social recommendation. In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., and Scarlett, (eds.), Proceedings of the 40th International Conference Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 36174-36192. PMLR, 23-29 Jul 2023.
Zhang, Y., Zhu, H., Song, Z., Koniusz, P., and King, I. Costa: Covariance-preservingg feature augmentation for graph contrastive learning. In Proceedings of the 28th ACM SIGKDD Conference Knowledge Discovery and Data Mining, KDD '22, pp. 2524-2534, New York, NY, USA, 2022a. Association for Computing Machinery. ISBN 9781450393850.
Wang, Y., Wang, W., Liang, Y., Cai, Y., and Hooi, B. Cur-
graph: Curriculum learning for graph classification. In Proceedings of the Web Conference 2021, WWW '21, pp- 1238-1248 New York, NY, USA, 2021b. Association for Computing Machinery.
Zhang. Y., Wang, X., Chen, H., Fan, J., Wen, W., Xue, H., Mei. H., and Zhu, W. Large language model with currieulum reasoning for visual concept recognition. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 6269-6280, 2024.
Wheeden, R., Wheeden, R. I.,, and Zygmund, A. Measure and Integral: An Introduction to Real Analysis. 1977.
Wu, 7.,, Ramsundar, B., Feinberg, E. N., Gomes, J., Ge- niesse, C., Pappu, A. S., Leswing, K., and Pande, V. Moleculenet: benchmark for molecular machine learn- ing. Chemical science, 9(2):513-533) 2018.
Zhang, Z., Cui, P., and Zhu, W. Deep learning on graphs: A survey. TKDE, 2020.
Zhang, Z., Cui, P., Pei, J., Wang, X., and Zhu, W. Eigen-gnn: A graph structure preserving plug-in for gnns. TKDE, 2021b.
Xu, D., Cheng, W., Luo, D., Chen, H., and Zhang, X. In- fogel: Information-aware graph contrastive learning. In Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Informa- tion Processing Systems, volume 34, pp. 30414-30425. Curran Associates, Inc., 2021.
Zhang, Z., Wang. X., Zhang, Z., Li, H., Qin, Z., and Zhu, W. Dynamic graph neural networks under spatio-temporal distribution shift. In Thirty-Sixii Conference on Neural Information Processing Systems, 2022b.
13

---

Self-supervised Masked Graph Autoencoder via Structure-aware Curriculum
Zhang, Z., Zhang, Z., Wang, X., and Zhu, W. Learning solve travelling salesman problem with hardness-adaptive curriculum. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pp. 9136-9144, 2022c.
Zhang, Z., Wang, J., and Zhao, L. Relational curriculum learning for graph neural networks, 2023a.
Zhang, Z., Wang, X., Zhang, Z., Qin, Z., Wen, W., Xue, H., Li, H., and Zhu, W. Spectral invariant learning for dynamic graphs under distribution shifts. Advances in Neural Information Processing Systems, 36:6619-6633, 2023b.
Zhao, M., Wu, H., Niu, D., and Wang, X. Reinforced curriculum learning on pre-trained neural machine trans- lation models. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 9652-9659, 2020.
Zhao, P., Pan, Y., Li, X., Chen, X., Tsang, I. W., and Liao, L. Coarse-to- coasse-to-fiee contrastive learning on graphs. IEEE Transactions on Neural Networks and Learning Systems, pp. 1-13, 2023. doi: 10. (00.0//NNNSSS.22..22222222.
Zhao, Z., Li, Y., Zou, Y., Tang, J., and Li, R. Masked graph autoencoder with non-discrete bandwidths. In Pro- ceedings of the ACM Web Conference 2024, WWW '24, pp. 377-388, New York, NY, USA, 2024. Association for Computing Machinery. ISBN 9798400701719, doi: 10.1 0o.114543899333365577700
Zhou, Y., Wang, X., Chen, H., Duan, X., Guan, C., and Zhu, W. Curriculum-nas: Curriculum weight-sharing neural architecture search. In Proceedings of the 30th ACM International Conference on Multimedia, pp. 6792-6801, 2022.
Zhou, Y., Wang, X., Chen, H., Duan, X., and Zhu, W. Intra- and inter-mont modal curriculum for multimodal learning. In Proceedings of the st ACM International Conference on Multimedia, pp. 3724-3735, 2023.
Zhou, Y., Pan, Z., Wang, X., Chen, H., Li, H., Huang, Y., Xiong. Z., Xiong, F., Xu, P., Zhu, W., et al. Curbench: cur- riculum learning benchmark. In forty-first International Conference on Machine Learning, 2024.
Zhu, J., Zeng, W. Zhang, J., Tang, and Zhao, X. Cross- view graph contrastive learning with hypergraph. Inf. Fusion, 99(C), nov 2023. ISSN 1566-2535.
Zhu, Q., Du, B., and Yan, Self-supervised training of graph convolutional networks, 2020.
Zhu, Y., Xu, Y., Yu, F. Liu, Q. Wu, S., and Wang, L. Graph contrastive learning with adaptive augmentation. In Proceedings of the Web Conference 2021 (WWW '21), pp. 2069-2080. ACM, 2021.
14

---

Self-supervised Masked Graph Autoencoder via Structure-aware Curriculum
In the Appendix, begin by summarizing the key notations in Section A. Then, we prove the convergence of our proposed method in Section B. We further elaborate related works in Section C. Additional experimental details are provided in Section D. In Section E, we further analyze the time and space complexity to demonstrate the efficiency of our method. Finally, the visualization of the synthetic dataset is shown in Section F, and we present additional experimental results in Section G.
A. Notations
The key notations are summarized in Table 4.
Table 4. Notations.
Notation
Deseription
Node set
Edge set
Emisk
Masked edges
X
Node feature matrix
Adjacency matrix
Amask A (4)
Adjacency matrix of the masked edges
Adjacency matrix of curriculum selected edges step Adjaceney matrix the difficult-hased selected edges
Anes
ARES
Adjacency matrix of the muddom-based selected edges
As
Adjacency matrix of reconstructed edges
Predicted adjacency matrix
LSSL
Loss function for self-supervised learning
CSPOL
Loss function for self- paced curriculum learning
(R)
Embedding of node at the k-th layer
N.
Set of direct neighbors of node
COM()
Combination function for updating node embeddings
AGG() N
Aggregation function for neighborhood information
Number of nodes
E d ENC() DECO) Re K I K g()
Number of edges
Dimensionality of embeddings Encoder
Decoder
Edge representation between nodes and u layer
Number of layers
Number of neighbors per node for aggregation
Number of edges that need be masked the training process Predicted probability of the presence
existing edge
Edge selection matrix step
Regularization coefficient taking control of the number of edges to be selected Balancing hyper-parameter l2 norm
GNN model parameter
Training transition smoothing regularizer coefficient
B. Theoretical Analyses
Following the work (Zhang et al., 2023a), we have the following convergence guarantees for Algorithm 1:
B.I. Proof of Theorem
Proof. Assuming the second-order derivatives of LSSt and f(S; A, A) are continuous, and given that the sequence (w(t), S()) is bounded, the second-order derivatives of LSSt. and f(S: X, A) are also bounded (Zhang et al., 2023a). This implies that
max {|| Cxssx / sp.
(6)
where p > a constant.
15

---

Self-supervised Masked Graph Autoencoder via Structure-aware Curriculum
In addition, the second-order derivatives of the reconstruction term Σis
Siz
|As - -4
are also bounded, which implies
max
V
Sig i
Aij
10
V' 5 Sig
Ars - A3
9,
2,
where q > 0 is a constant and Á is a function of w.
As result, the objective function Call is bi-smooth, i.e..
max [ Lart
V& || S p g.
and Lall satisfies Assumption in (Li et al., 2019b). Therefore, according to Theorem 10 in (Li et al., 2019b), the second- order derivative of Lail is continuous, and for any y > p + q. any bounded sequence (())) generated by Algorithm 1 almost surely avoids convergence to strict saddle point of Lau (Zhang al., 2023a).
B.2. Proof of Theorem
Proof. As established in the previous proof, the objective function Call satisfies Assumption 4 in (Li et al., 2019b).
Furthermore, since (ssi(X, A A((-1); w). ((; X, A), and Ei, Siyl - A all satisfy the hurdyka-tojasiewiice (KI.) property, the composite objective Caul also satisfies the KL property. As shown previously, Caul is continuous. In addition, according to the results in (Wheeden et al., 1977), the continuous differentiability of Cas implies that its gradient is Lipschitz continuous. Therefore, Lall satisfies Assumption 1 in (Li et al., 2019b). Since Lall satisfies both Assumptions and 4, we can invoke Corollary 3 in (Li et al., 2019b) conclude that for any y > p + 9, any bounded sequence (w)))(()))) generated by Algorithm will almost surely converge to second-order stationary point of Can (Zhang et al., 2023a).
C. Additional Related Works
Here we provide additional discussions on related work in the areas of graph neural networks (GNNs) and graph adversarial training. complementing our earlier review on graph self-supervised learning and curriculum learning.
Graph Neural Networks. Graph-structured data are ubiquitous across a wide range of worldworld applications (Hu et al., 2020a; Li al., 2019a; 2021a). The emergence of graph neural networks (GNNs) (Kipf & Welling, 2017; Veličković et al., 2018; Xu et al., 2019; Li et al., 2022b; Cai et al., 2024; Li et al., 2023c; Zhang et al., 2023b; Li et al., 2025; Chen et al., 2025) has led to significant advances in graph representation learning (Zhang et al., 2020), demonstrating strong performance in tasks such as node classification (Kipf & Welling, 2017), link prediction (Zhang & Chen, 2018), and graph-level classification (Xu et al., 2019). GNNs have also shown promise in high-impact domains including drug discovery (Wu et al., 2018), protein function prediction (Jiang et al., 2017), and traffic forecasting (Jiang & Luo, 2021). These models typically rely on neighborhood aggregation or message-passing mechanisms, where node representations are iteratively refined by aggregating information from local neighbors (Veličković et al., 2018: Xu et al., 2019). Despite their success, many offte-of-the-arr GNNs (Ma et al., 2019; Ji et al., 2021; Fan et al., 2021; Gao et al., 2021; Miao et al., 2021; Ye & Ji, 2021; Zhang et al., 202 bb; 2022b; Li et al., 2022d;a) require end-to-end supervised training with task-specific labels, which are often scarce or expensive to obtain (Feng et al., 2023). In contrast, our proposed method adopts a generative self-supervised framework that reduces dependence on labeled data, making it more suitable for large-scale or label-deficient graph datasets.
Graph Adversarial Training. Graph adversarial training is a robust learning paradigm that enhances model generalization and stability by introducing adversarial perturbations or generating adversarial examples. These methods typically involve generator-diserimnnade setup, where the generator attempts to craft perturbations or fake samples to deceive the discriminator, which in turn is trained to resist such attacks. For example, GraphGAN (Wang et al., 2018) introduces adversarial training into graph representation learning by generating synthetic links and learning to discriminate between real and fake connections. ARGA and ARVGA (Pan et al., 2020) enforce the latent representations to match given prior distribution using adversarial regularization, followed by graph reconstruction. GCA (Zhu et al., 2021) leverages centrality- based graph augmentations to emphasize critical structures and adaptively perturb unimportant components. AUG-MAE (Wang al., 2024) introduces an adversarial masking strategy to generate hard-to-align node features, thereby
16

---

Self-supervised Masked Graph Autoencoder via Structure-aware Curriculum
improving contrastive alignment. Unlike these adversarial learning approaches, our curriculum-based masking strategy explicitly defines a progression from easy hard reconstruction tasks. This structured learning path is fundamentally distinct from adversarial objectives and focuses improving representation learning by aligning the training dynamics with task difficulty.
D. Additional Experimental Details
D.1. Dataset Statisties
We summarize the statistics of the real-world datasets used in our experiments in Table For datasets from the OGB benchmark, we follow the standardized experimental protocol, which provides predefined train/validationttes splits. According to the official guidelines, validation labels are intended solely for hyperparameter tuning and are not permitted to be used during model training. Notably, the OGB guidelines specify an exception for the OGBL-collab dataset, where an alternative protocol allows the use of validation labels during training. However, for consistency and fairness across experiments, we adopt the stricter protocol for all three OGB link prediction datasets used in this study- Maady-OGGL-collahh where validation labels are excluded from the training process.
OGBL-ddi, and OGBL-ppa- -eeeee
Table Summary of dataset statistics.
Dataset
# Nodes
Edges
Features
Train/Val/Test
# Classes
Cora
2,708
5,429
1,433
85/5/10
Citescer
3,312
4,660
3,703
85/5/10
6
Pubmed
19,717
44,338
500
85/5/10
3
Coauthor-CS
18.333
81,894
6,805
15
Coauthor- Physics
Coauthor-Physics
34,493
247.962
8,415
ogbn-arxiv
169,343
1,166,243
128
40
OGBL-ddi
4,267
1,334,889
80/10/10
OGBL-collab
235,868
1,285,465
128
92/4/4
OGBL-ppa
576,289
30,326,273
58
70/20/10
D.2. Dataset License
The datasets included in this work are publicly available as follows:
1. Plantoid Datasets:
http://sh.....oooommooo//////aan with MIT License.
2. Coauthor Datasets: http://th...asssaaaaaccaeeeeeenm with MIT License.
3. Open Graph Benchmark (OGB): http::///gbbsaattoo.o.......o//p with MIT License.
D.3. Implementation Details
We implement our models using PyTorch and employ Stochastic Gradient Descent (SGD) the optimizer. The number of training epochs is set to 400 for node classification tasks and 200 for link prediction tasks, with early stopping patience of 50 steps.
Our model supports various pusssage-passing GNNs, and we adopt GCN (Kipf & Welling, 2017) and GraphSage (Hamilton et al., 2017) as the primary backbones in our experiments. For large-scale datasets from the OGB benchmark -oaimarkk-GB-----. OGBN-arxis OGBN-ddi, OGBL-collab, and OGBL-ppa AGGBL-ppa-w- we set the representation dimensionality 256 and use a 3-layer GNN. For all other datasets, we set 128 and use 2-layer GNN.
The cross-correlation decoder is implemented
two-layer multilayer perceptron (MLP) with ReLU activation, and its hidden dimension is selected from {128, 256, 512, 1024). The values for splil ratio and mask ratio are tuned within the ranges [0, 1] and [0.4, 1] (with step size of 0.1), respectively. The dropout rate is chosen from (0.3, 0.4, 0.5, 0.6).
The hyperparameter À controls the number of edges selected during training. larger À promotes the selection of more edges for masking and reconstruction. To facilitate an easy-to-han curriculum learning scheme, i.e. progressively increasing the difficulty of the training samples by masking more edges, the number of masked edges K should increase over training
17

---

Self-supervised Masked Graph Autoencoder via Structure-aware Curriculum
steps. Accordingly, is designed increase with the iteration step following the schedule below (Zhang et al., 2023a):
Angal
ift
T- G
Ainitial
otherwise,
where T denotes the total number of training epochs, and the current training step. This scheduling rule can be adapted support alternative pacing strategies if needed.
For node classification, we evaluate the learned node representations using downstream linear SVM classifier. We report the average 10-fold cross-validation accuracy with standard deviation over three repeated runs. For link prediction, we randomly sample an equal number of negative edges as positive ones to compute the AUC score. Results are reported as the mean and standard deviation over five repeated runs. Unless otherwise specified, all remaining hyperparameters are kept consistent with the settings in S2GAE (Tan et al., 2023) to ensure a fair comparison.
D.4. Hardware and Software Configuration
We conduct the experiments with the following hardware and software configurations:
Operating System: Ubuntu 20.04.6 LTS
CPU: Intel(R) Xeon(R) Gold 6348 CPU@2.60GHZ
GPU: NVIDIA GeForce RTX 4090 GPU
Software: Python 3.8.13; PyTorch 2.0.1; PyTorch Geometric 2.3.1.
E. Additional Complexity Analysis
E.1. Time Complexity Analysis
To further assess the efficiency of our method in practice, we compare its training time per epoch against the strong baseline S2GAE (Tan al., 2023) under identical hyperparameter settings. We report the average training time and standard deviation per epoch in Table 6. The results demonstrate that proposed Cur-MGAE model achieves superior efficiency compared S2GAE.
Table 6. Empirical Time Comparisons.
Link Prediction
Node Classification Citeseer
Cora
Citeseer
OGBL-ppa
Cora
OGBN-arxiv
Cur-MGAE
0.045 + 0.003s
0.043 + 0.004s
79.1 + 1.753s
0.093 # 0.020s
0.089 + 0.015s
1.718 + 0.593s
S2GAE
0.048 # 0.008s
0.045 # 0.009s
77.469 + 1.224s
0.100 = 0.020s
0.098 + 0.009s
2.600 + 0.357s
E.2. Space Complexity Analysis
As for space complexity, our model adopts GCN and GraphSAGE as backbone architectures, whose space complexities are given by O x d++E+ Σ di-1 x di N x Σx= di) and O(N x d E+ x I +EK di x di +N x Σ di), respectively. Here, N denotes the number of nodes, the number of edges, the input feature dimension, K the number of GNN layers, d and d, the input and output dimensions at layer I, and I the number of neighbors per node used in aggregation. Beyond the GNN backbones, our model introduces a complexity-gune -uiiiey--gdieddddee curriculum masking module and a self-paced mask scheduler, both of which incur an additional space complexity of O(E). These modules are lightweight and do not increase the overall space complexity beyond the standard GNN frameworks. Therefore, the space complexity of our model remains comparable to that of existing methods.
To complement the theoretical analysis, we empirically compute the number of parameters of our proposed model and various baseline methods under a unified configuration, where the embedding dimension is set to 128. The results are presented in Table 7, with all parameter counts calculated on the Cora dataset. For GraphMAE, we follow the original setup by using a GAT backbone with 4 attention heads.
18

---

Self-supervised Masked Graph Autoencoder via Structure-aware Curriculum
Table Comparison of total number of parameters models.
GraphMAE (Hou et al., 2022) MaskGAE (I.i ct al., 2023d) S2GAE (Tan et et., 2023)
Cur-MGAF
Number of Parameters
419,253
266,370
282,369
291,871
We observe that, despite the introduction relatively complex components, our method maintains a comparable number of parameters those of the baseline models.
F. Synthetic Dataset Visualization
Following previous work (Karimi et al., 2018; Abu-El-Haija et al., 2019; Zhang et al., 2023a), we build the synthetic dataset shown in Figure 3 to test the curriculum schedule and performance of our proposed model. Each point represents a node, with its z and y coordinates sampled from overlapping Malti-Gaussian distributions. The nodes are categorized into 10 classes based on their features, and the corresponding classes are indicated by different colors. The difficulty of each edge determined based on the relationship between the labels of its incident nodes: edges connecting nodes with the same label considered easy, edges connecting nodes with adjacent labels medium, and edges connecting nodes with non-adjacent labels categorized hard.
Figure Visualization of the synthetic dataset. Fach synthetic graph consists 5,000 nodes, which are assigned one of classes based their features. Edges generated according to probability that decreases with the cyclic distance between node labels. Specifically, the connection probability between nodes u and e proportional to lou-ool, where |c., cul denotes the minimal cyclic distance between labels and in circular label spacc.
G. Additional Experiments
G.1. Additional Comparisons with Contrastive Graph SSL Methods
Since the majority of the aforementioned baselines adopt generative paradigms, we additionally compare node classification performance of representative contrastive graph self-supervised methods to provide more comprehensive evaluation, as shown in Table 8.
19

---

Self-supervised Masked Graph Autoencoder via Structure-aware Curriculum
Table Node classification accuracy (%) of our proposed method compared with contrastive baselines. Bold values indicate the hest performance across all methods. indicates that the method was not evaluated on the dataset due to unavailable code or omitted experiments in the original paper. Rank denotes the average performance rank across datasets. method achieves the highest accuracy across all datasets.
Cora
Citeseer
Coauthor- Physccs
Rank
GMI (Peng ct al., 2020)
82.4 + 0.6
71.7 + 0.2
12.83
InfoGCL (Xu ct al., 2021)
83.5 + 0.3
73.5 = 0.4
9,33
CCA-SSG (Zhang al., 2021a)
84.2 0.4
73.1 0.3
95.38 + 0.06
7.50
GCA-EV (Yu et al., 2023)
95.73 + 0.03
10.67
AF-GCL (Wang et al., 2022a)
0.1
72.1 + 0.4
95.75 + 0.15
7.17
AFGRL (Lee et al., 2022)
0.2
68.7 $ 0.3
95.69 + 0.10
7.67
SUGRL (Mo ct al., 2022)
0.5
73.0 = 0.4
95.38 + 0.11
6,33
C2F (Zhao al., 2023)
94.09
8,33
COSTA-SV (Zhang ct al., 2022a)
0.3
72.8 + 0.3
95.74 + 0.02
5.50
COSTA-MI MMV (Zhang et al., 2022a)
8.2
72.9 0.3
95.60 + 0.02
5.00
IAG (Sun et al., 2023a)
86.1
73.6
4.00
S*-CL (Ding ct al., 2023)
0.4
74.6 + 0.4
3,33
11-GCL (Zhu et al., 2023)
0.5
74,2 # 0.3
2.83
IGCL et al., 2023a)
0.1
6.12
95.85 + 0.10
2.67
PHASES (Sun et al., 2023b)
95.82 + 0.11
2.67
MA-GCL (Gong et al.. 2023)
0.4
0..
2.00
Cur-MGAE
0.6
74.7 # 0.4
95.91 # 0.05
1.00
G.2. Experiment Results on Synthetic Datasets
We further conduct node classification and link prediction experiments on three synthetic datasets with varying levels of homophily, characterized by homophily coefficients of 0.1, 0.5, and 0.9 (denoted as Homo = 0.1, 0.5, and 0.9). Two representative baselines are adopted for comparison, and we report both node classification accuracy and link prediction AUC in the following table.
Table 9, Results on synthetic datasets.
Homo=0.1
Homo=0.5
Homo=0,9
Link Pred.
Node Class.
Link Pred.
Node Class.
Link Pred.
Node Class.
Cur-MGAE
52.73 2,56
46.79 = 0.11
57.20 0.12
82.76 0.67
80.97 # 0.36
99.96 0.02
S2GAE(Tan al., 2023)
50.04 0.08
34.09 + 0.13
51.28 1.27
81.90 = 0.17
80.48 + 0.39
98.86 0.00
BGRI,(Thakorr et al., 2022)
51.84 + 1.88
22.93 = 1.38
53.46 # 0.02
40.07 = 4.40
80.68 # 0.55
73.73 0.68
The results show that our model consistently achieves the highest accuracy across all settings for both link prediction and node classification tasks. This demonstrates the effectiveness of the proposed structure-aware curriculum in learning powerful and informative node representations.
G.3. Hyperparameter Sensitivity
We investigated the sensitivity of some important hyperparameters of our method.
Effectiveness of the split ratio. The split ratio is a critical hyperparameter that introduces randomness into the edge selection process, thereby helping mitigate overfitting. It determines the proportion of masked edges selected based on the difficulty-awan strategy. A lower split ratio implies that more edges are selected randomly, while value of indicates full reliance on difficulty-basee selection. Specifically, when the split ratio is O, edge masking is entirely random; when it is 1, edge selection is entirely fifcuult-guuieed As illustrated in Figure 4, an appropriately chosen split ratio strikes a balance between exploitation (leveraging informative edges) and exploration (incorporating diverse edge patterns), thereby enhancing overall model performance.
20

---

Self-supervised Masked Graph Autoencoder via Structure-aware Curriculum
Results on Cora
Accuracy (96
88
Accuracy (%)
88
Accuracy (%6
88
86
86
86
84
mask ratio=0.8
split ratio=0.1
split ratie=0.1
ratio=0.5
spllt ratio=0.5
split ratio=0.5
82
82
82
0.0
0.5
1.0
0.4
0.6
0.8
5
split ratio (Aintial
1)
mask ratio MMnia
1)
Amiiaal (mask ratio 0.8)
Results on PubMed
93
93
93
Accuracy (%6
92
Accuracy (%)
92
92
Accuracy
90
90
90
ratio=0.8
split
split
mask ratio-0.5
split ratio-0.5
split ratic-0.5
89
89
89
0.0
0.5
1.0
0.4
0.6
0.8
1
5
split ratio (Ainital 1)
mask ratio Miiieel = 1)
Annial (mask ratio = 0.8)
Figure 4. Impact of split ratio, mask ratio, and Aiiital model performance, based node classification results Cora and Pubmed.
Effectiveness of the mask ratio. The mask rutio specifies the maximum proportion edges that can be masked during training. A small mask ratio restricts the number of masked edges, limiting the model's 's exposure sufficient learning signals and potentially trapping it in overly simple pretext tasks (e.g., predicting 10% of the edges using the remaining 90%). Conversely, an excessively high mask ratio (e.g.. predicting 90% of the edges from only 10%) may lead to overly challenging tasks that degrade learning quality. Hence, selecting an appropriate mask ratio is essential for ensuring the training process remains both effective and stable.
Effectiveness of Ainitial- The hyperparameter Amitial governs the pace the structure-aware curriculum learning schedule. As shown in Figure 4, setting Ammial = yields optimal performance on the Cora dataset. A smaller Aiiiial may lead to inadequate exposure to masked edges, limiting training diversity and reducing performance. On the other hand, a large Ainirial can result in the model being prematurely exposed difficult tasks, which hampers carly-stage learning. well-chosen Ainital enables smooth progression from simple complex tasks, avoiding overfitting trivial edges while ensuring sufficient challenge during training. It reflects the significance of the structure-aware curriculum learning strategy of the proposed method.
21


Reviews:
[{"review_id": "eTx3O2ss3n", "reviewer": "Reviewer_PaJ7", "summary": "The authors explore generative graph self-supervised learning by integrating curriculum learning into a masked graph autoencoder framework. The innovation lies in introducing a structure-aware curriculum strategy that trains the model from easy to hard reconstruction tasks. Specifically, they propose a complexity-guided difficulty measurer to quantify edge reconstruction difficulty based on residual errors and a self-paced scheduler to dynamically adjust the masking ratio and edge selection during training. This approach aims to align task difficulty with the model’s evolving capabilities, addressing the limitation of existing methods that treat all edges equally. Experimental results across node classification and link prediction benchmarks (Cora, Citeseer, OGB datasets) demonstrate state-of-the-art performance, with improvements on large-scale datasets like OGBL-ppa. Theoretical proofs for convergence and ablation studies further validate the design.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1:** Missing key notations in Figure 1.\n\nThank you for this comment. We will add the key notations, e.g., $\\mathcal{E}_{mask}$, $\\lambda$, and $\\omega$ as well as the legend in Figure 1.\n\n\n\n**W2:** Standard deviations of the empirical training time.\n\nWe have updated the Table 7 to report the average training time and the standard deviation per epoch as follows (LP: link prediction; NC: node classification).\n\n|          | LP          | LP          | LP           | NC          | NC          | NC          |\n| -------- | ----------- | ----------- | ------------ | ----------- | ----------- | ----------- |\n|          | Cora        | Citeseer    | OGBL-ppa     | Cora        | Citeseer    | OGBN-arxiv  |\n| Cur-MGAE | 0.045±0.003 | 0.043±0.004 | 79.117±1.753 | 0.093±0.020 | 0.089±0.015 | 1.718±0.593 |\n| S2GAE    | 0.048±0.008 | 0.045±0.009 | 77.469±1.224 | 0.100±0.020 | 0.098±0.009 | 2.600±0.357 |\n\nThe results above show the efficiency of our method and scalability to the large graph.\n\n\n\n**W3:** Discussion of the hyperparameter study.\n\nWe have added another dataset Pubmed for hyperparameter sensitivity study, and the results (accuracy) are shown in the following tables. And we will plot the figure in the revised paper.\n\n| Split ratio ($\\lambda_{initial}$ = 1) | 0.0         | 0.2        | 0.4        | 0.6        | 0.8        | 1.0        |\n| ------------------------------------- | ----------- | ---------- | ---------- | ---------- | ---------- | ---------- |\n| mask ratio=0.5                        | 84.70±0.34  | 84.94±0.18 | 84.97±0.23 | 85.00±0.14 | 84.73±0.10 | 85.09±0.09 |\n| mask ratio=0.8                        | 85.20± 0.20 | 85.30±0.23 | 85.29±0.15 | 85.21±0.25 | 85.14±0.19 | 85.14±0.08 |\n\n| mask ratio ($\\lambda_{initial}$ = 1) | 0.4        | 0.5        | 0.6        | 0.7        | 0.8        | 0.9        |\n| ------------------------------------ | ---------- | ---------- | ---------- | ---------- | ---------- | ---------- |\n| split ratio=0.1                      | 84.91±0.24 | 85.02±0.23 | 84.94±0.12 | 84.89±0.22 | 84.86±0.14 | 85.02±0.10 |\n| split ratio=0.5                      | 84.91±0.12 | 84.89±0.11 | 85.08±0.13 | 84.74±0.14 | 84.92±0.18 | 85.36±0.17 |\n\n| $\\lambda_{initial}$ (mask ratio = 0.8) | 0.5        | 1.0        | 2.0        | 3.0        | 4.0        | 5.0        |\n| -------------------------------------- | ---------- | ---------- | ---------- | ---------- | ---------- | ---------- |\n| split ratio=0.1                        | 85.17±0.22 | 84.86±0.14 | 84.96±0.20 | 85.17±0.15 | 85.26±0.15 | 85.05±0.16 |\n| split ratio=0.5                        | 85.13±0.07 | 84.92±0.18 | 85.02±0.14 | 84.92±0.53 | 85.34±0.07 | 85.39±0.13 |\n\nBesides, we have also revised the discussions as follows. \n\n**Effectiveness of split ratio.** *Split ratio* is an important hyperparameter for adding randomness in edge selection to overcome overfitting. It represents the percent of the masked edges come from the difficulty-based selection. A small *split ratio* represents that more edges are selected randomly. Specifically, when *split ratio* is 0, the model completely selects edges randomly. When *split ratio* is 1, the model selects edges completely relying on the difficulty-based strategy. As shown in Figure 4,  a proper *split ratio* can help with balancing exploitation and exploration and achieve promising results.\n\n**Effectiveness of mask ratio.** *Mask ratio* defines how many edges can be masked at the maximum. On the one hand, when *mask ratio* is small, few edges can be masked, and the model can not make full use of the data for training, which will be trapped in the easy pretext tasks (e.g., predicting 10% of the edges with the left 90% of the edges). On the other hand, if the model is trained to finish hard reconstruction tasks (e.g., predicting 90% of the edges with the left 10% of the edges), it can be difficult to obtain the informative node representation in practice. Thus, setting a proper *mask ratio* is important during the training process.\n\n**Effectiveness of $\\lambda_{initial}$.** $\\lambda_{initial}$ influences the pace of the structure-aware curriculum. As shown in Figure 4, $\\lambda_{initial}=1$ is good enough on Cora dataset. A small $\\lambda_{initial}$ can lead to performance drops because of the lack of enough training data. And a large $\\lambda_{initial}$ may force the model to handle difficult tasks at the initial training stage. A proper $\\lambda_{initial}$ helps avoids premature exposure to overly complex tasks and also mitigates the risk of overfitting to easy edges, allowing the model to maintain a balance between focusing on predictable edges and exploring more challenging ones. It reflects the significance of the structure-aware curriculum learning strategy of the proposed method.", "claims_and_evidence": "The claims regarding performance improvements are supported by extensive empirical evaluation of node classification and link prediction tasks. The theoretical guarantees on convergence, including avoidance of saddle points and second-order convergence, provide additional supports to the claims.", "methods_and_evaluation_criteria": "The methodology is clearly described. It uses a GNN encoder and a novel cross-correlation decoder that concatenates multi-layer node embeddings via element-wise products, enhancing edge representation. In curriculum masking, edges are masked based on residual errors with easier edges prioritized early in training. The self-paced scheduler balances exploration and exploitation via a split ratio hyperparameter, gradually increasing masked edges while avoiding overfitting.\n\nThe evaluation is comprehensive, using widely accepted benchmarks (Cora, Citeseer, OGB datasets), including both small-scale and large-scale ones. The proposed masking and reconstruction strategy is interesting, and the comparisons against existing contrastive (DGI, BGRL) and generative SSL methods (GraphMAE, S2GAE) are also comprehensive. The evaluation metric (accuracy, AUC, and Hits@N) in each dataset follows standard protocol.", "theoretical_claims": "The paper provides theoretical justification for the proposed curriculum learning framework. By leveraging bi-smooth objectives and KL properties, the authors show that the alternating optimization avoids strict saddle points and converges to second-order stationary points. The assumptions are reasonable.", "experimental_designs_or_analyses": "The experimental setup is good, with appropriate baselines, fair comparisons, and ablation studies to validate each component. However, a more detailed discussion on hyperparameter sensitivity could further strengthen the study.", "relation_to_broader_scientific_literature": "The work is well-situated within the literature on self-supervised learning, curriculum learning, and graph representation learning. The authors adequately discuss prior methods and their limitations.", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "### Strength:\n- The paper introduces a novel structure-aware curriculum strategy into masked graph autoencoders, dynamically adjusting task difficulty from easy to hard edges based on residual errors, which addresses the limitation of uniform treatment of edges in existing methods.\n- Extensive experiments on diverse benchmarks demonstrate significant improvements over state-of-the-art baselines, validating the method’s effectiveness across both small- and large-scale datasets.\n- The convergence guarantees are rigorously proven under reasonable assumptions, and synthetic dataset experiments further enhances the theoretical claims.\n\n### Weaknesses:\n- Figure 1 misses the key notations used in the method, which makes difficulties to quickly understand the technical details.\n- While time complexity is discussed, empirical training time comparisons lack standard deviations.\n- The hyperparameter study has limited discussions on results.", "other_comments_or_suggestions": "The hyperparameter sensitivity is only conducted on one dataset.", "questions_for_authors": "1. Could you add annotations or a caption legend to the flows in the framework figure? \n\n2. Could you provide standard deviations for training times comparisons?", "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": "", "extra_scores": {}}, {"review_id": "5sOZseGETE", "reviewer": "Reviewer_V46k", "summary": "This paper introduced a novel masked graph autoencoder with a structure-aware curriculum learning strategy. The key idea was to mask edges in an easy-to-hard manner, improving representation learning. The joint framework to recover the missing edge of the input based on the unmasked graph structure and schedule the training edges for reconstruction in a proposed self-paced learning manner, so that the GNN encoder was trained more effectively. The method was evaluated on several benchmarks, showing strong performance gains. The authors provided solid theoretical analyses and empirical validations.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback. We addressed all the comments. Please kindly find the detailed responses to the comments below.  \n\n**W1.1:** The caption of Figure 3.\n\nThanks for this suggestion. We would like to revise the caption of Figure 3 into \"Visualization of the synthetic dataset. Each synthetic graph includes 5,000 nodes. The nodes are then classified into 10 labels based on the node features. The edges are generated with a probability that correlates with the node labels. The edge formation likelihood between a node $u$ and a node $v$ is proportional to $e^{|c_u-c_v|}$, where $|c_u-c_v|$ denotes the minimal cyclic distance between the labels in a circular label space.\" We will update it in the revised paper.\n\n\n**W1.2:** Typos.\n\nThank you for this comment. We have carefully proofread the paper and revised the typos:\n\n- line 312 (left): the sentence is revised into \"So it has unsatisfactory performances on larger-scale benchmarks\"\n\n- line 880: the sentence is revised into \"The result is shown in Table 7, from which we can find that our proposed Cur-MGAE model is also more efficient than S2GAE.\"\n\n\n**Q1**: How does the proposed method scale to large graphs?\n\nThank you for this comment. We would like to clarify that our method can scale to large graph considering its good time and space complexity. Specifically, we adopted the message-passing GNNs whose time complexity is $O(Ed+Nd^2)$, where $N$ and $E$ represent the total number of nodes and edges in the graph, and $d$ is the representation’s dimensionality. The time complexity of the decoder and the self-paced mask scheduler are both $O(Ed)$, because we calculate the residual error for each edge. Instead of all $N\\times N$ potential edges, only existing edges of the input graph are considered to be selected. Therefore, the time complexity of the complexity-guided curriculum masking is $O(E)$.  For this reason, the overall time complexity of our model is $O(Ed+Nd^2)$, which is on par with that of other GNN-based graph representation methods, which is also $O(Ed+Nd^2)$, demonstrating good scalability to large graphs. Empirically, we also tested our model on large graphs, e.g., OGBN-arxiv, which has 169,343 nodes and 1,166,243 edges, and OGBL-ppa, which has 576,289 nodes and 30,326,273 edges. We also conducted experiment to compare the training time on such large graph. The following table reports the training time per epoch, which is acceptable and also comparable with the baseline S2GAE.\n\n|          | OGBL-ppa (E=30,326,273, N=576,289) | OGBN-arxiv (E=1,166,243, N=169,343) |\n| -------- | ---------------------------------- | ----------------------------------- |\n| Cur-MGAE | 79.117±1.753                       | 1.718±0.593                         |\n| S2GAE    | 77.469±1.224                       | 2.600±0.357                         |\n\nIn addition, since we adopt GCN and GraphSAGE as our backbone model, the space complexity is  $O(N \\times F + E + \\sum^{K}\\_{l=1}F_{l-1} \\times F_{l} + N \\times \\sum^K_{l=1}F_l)$ and $O(N \\times F + E + N \\times I^K +  \\sum^{K}\\_{l=1}F_{l-1} \\times F_{l} + N \\times \\sum^K_{l=1}F_l)$ respectively, where $F$ is the feature dimension, $N$ is the number of nodes,  $E$ is the number of edges, $K$ is the number of layers, $F_{l-1}$ and $F_l$ are the input and output feature dimensions of layer $l$, and $I$ is the number of neighbors sampled per node at each layer. And the space complexity of the proposed complexity-guided curriculum masking module and self-paced mask scheduler are both $O(E)$, which do not bring higher space complexity. Therefore, our proposed model also has a comparable space complexity with the existing methods, making it easier to scale to large graphs.\n\nWe will add the discussions above in the revised paper.", "claims_and_evidence": "The claims are reasonable and supported by experimental results. The idea of curriculum learning for graph SSL is novel and well-motivated to me.", "methods_and_evaluation_criteria": "The approach makes sense for graph learning, and the evaluation is solid. The evaluations considered node classification and link predictions. The choice of datasets and baselines is appropriate.", "theoretical_claims": "The theoretical analysis is a nice addition to the practical results. The convergence analyses are important. The proofs are correct. But more intuitive explanations of the theorems are necessary.", "experimental_designs_or_analyses": "The experiments are well-designed, covering multiple datasets and comparisons. The baselines covered the state-of-the-art.", "relation_to_broader_scientific_literature": "Good coverage of related work, with clear distinctions from prior methods.", "essential_references_not_discussed": "No major gaps or mistakes were found.", "other_strengths_and_weaknesses": "Strengths: \n\nNovel curriculum learning idea in graph SSL setting, strong experimental results. \n\nWeaknesses: \n\nThe writing should be improved. For example, the caption of Figure 3 in line 956 is too short and meaningless. There are also some typos, e.g., line 312 (left), line 880, etc.", "other_comments_or_suggestions": "If possible, add a discussion on how the difficulty measurer and self-paced scheduler could generalize to larger graphs.", "questions_for_authors": "How does the proposed method scale to large graphs?", "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": "", "extra_scores": {}}, {"review_id": "vLMtnf5t6m", "reviewer": "Reviewer_s6T8", "summary": "In summary, the paper focuses on proposing a masked graph autoencoder enhanced with curriculum learning techniques. It formally defines a measure of edge difficulty to quantify reconstruction challenges, introduces a self-paced mask scheduler for progressively incorporating edges based on their difficulty, and provides solid theoretical convergence guarantees. Extensive experiments are conducted on several widely used benchmarks (including OGB) to demonstrate the effectiveness and generalizability of the proposed approach.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback. We addressed all the comments. Please kindly find the detailed responses to the comments below.\n\n**W1:** Comparison with adversarial training.\n\nThank you for this comment. Graph adversarial training is a learning paradigm that aims to improve model robustness by introducing adversarial perturbations or generating adversarial samples. It usually consists of a generator and a discriminator. The generator tries to generate samples to deceive the discriminator, while the discriminator tries to remain robust under such attacks. For instance, GraphGAN [1] introduces Generative Adversarial Network (GAN) into graph representation learning by proposing a generator to produce \"fake\" connections between nodes and a discriminator to distinguish between real and generated edges. ARGA and ARVGA [2] propose an adversarial training principle to enforce the encoded latent codes to match a prior Gaussian or Uniform distribution and further build a graph decoder to reconstruct the input graph. Based on node centrality measures, GCA [3] highlights important connectivity structures and proposes an adaptive graph enhancement method to destroy unimportant edges or features. AUG-MAE [4] designs an adversarial masking strategy on nodes to provide hard-to-align samples, which improves the alignment performance. Different from these methods, the curriculum-based masking explicitly defines an easy-to-hard pretext tasks for training GNNs, which has different goals compared with the graph adversarial learning method. We will add these discussions in our revised paper.\n\nIn addition, we compared AUG-MAE [4], which is a recent representative graph adversarial training work, in the experiments. The results show that our method consistently outputperforms this method.\n\n| Dataset      | Cora             | Citeseer         | Pubmed           | Coauthor-CS      | Coauthor-Physics | OGBN-arxiv       |\n| ------------ | ---------------- | ---------------- | ---------------- | ---------------- | ---------------- | ---------------- |\n| AUG-MAE      | 84.30 ± 0.40     | 73.20 ± 0.40     | 81.40 ± 0.40     | 92.15 ± 0.22     | 95.34 ± 0.60     | 71.90 ± 0.20     |\n| **Cur-MGAE** | **87.25 ± 0.55** | **74.68 ± 0.37** | **85.86 ± 0.14** | **92.69 ± 0.17** | **95.91 ± 0.05** | **73.00 ± 0.06** |\n\n\n\n**W2:** Dataset split is not clear.\n\nThank you for this comment. The dataset split in our experiment follows the same strategy in a representative work [5] for a fair comparison. We also summarized the train/validation/test split as well as the other statistics of the adopted datasets in the following table for better clarification.\n\n|                  | # Nodes | # Edges    | # Features | Train/Val/Test | # Classes |\n| ---------------- | ------- | ---------- | ---------- | -------------- | --------- |\n| Cora             | 2,708   | 5,429      | 1433       | 85/5/10        | 7         |\n| Citeseer         | 3,312   | 4,660      | 3703       | 85/5/10        | 6         |\n| Pubmed           | 19,717  | 44,338     | 500        | 85/5/10        | 3         |\n| Coauthor-CS      | 18,333  | 81,894     | 6,805      | -              | 15        |\n| Coauthor-Physics | 34,493  | 247,962    | 8,415      | -              | 5         |\n| ogbn-arxiv       | 169,343 | 1,166,243  | 128        | -              | 40        |\n| OBGL-ddi         | 4,267   | 1,334,889  | -          | 80/10/10       | -         |\n| OGBL-collab      | 235,868 | 1,285,465  | 128        | 92/4/4         | -         |\n| OGBL-ppa         | 576,289 | 30,326,273 | 58         | 70/20/10       | -         |\n\n\n\n**Q1:** Extension to graph classification tasks\n\nThank you for this comment. In this work, we mainly focus on node-level and link-level tasks. Since our method is able to learn powerful representations for each node with the structure-aware curriculum, it can easily obtain the graph-level representation with pooling functions or use similar techinique to schedule the training for each input graph in graph classification task. We will investigate this problem in the future.\n\n\n\n**References**\n\n[1] Wang et al., GraphGAN: Graph Representation Learning with Generative Adversarial Nets. AAAI, 2018.\n\n[2] Pan et al., Learning Graph Embedding with Adversarial Training Methods. ICLR, 2020.\n\n[3] Zhu et al., Graph Contrastive Learning with Adaptive Augmentation. WWW, 2021.\n\n[4] Wang et al. Rethinking Graph Masked Autoencoders through Alignment and Uniformity. AAAI, 2024.\n\n[5] Tan et al., S2GAE: Self-Supervised Graph Autoencoders are Generalizable Learners with Graph Masking. WSDM, 2023.", "claims_and_evidence": "The paper justifies the effectiveness of the proposed masked graph autoencoder framework by presenting solid theoretical analyses and extensive empirical evidence. The empirical evaluations demonstrate the superiority of the proposed method compared to state-of-the-art baselines in graph self-supervised learning.", "methods_and_evaluation_criteria": "The methods are carefully designed, particularly the self-paced scheduler and the difficulty measurer, which are innovative and are formulated in a good way.", "theoretical_claims": "The theoretical results are solid, with convergence guarantees that align with known resThe theoretical results are solid, with convergence guarantees that align with known results in curriculum learning and optimization.ults in curriculum learning and optimization.", "experimental_designs_or_analyses": "The experiments validate the main claims of the method. The compared baselines include representative and recent graph contrastive methods or masked graph autoencoders. The approach outperforms >10 baselines across different tasks (Tables 1 and 2).", "relation_to_broader_scientific_literature": "It relates to curriculum learning and generative graph SSL approaches.", "essential_references_not_discussed": "None missing. All key references are adequately covered in related work and experiments.", "other_strengths_and_weaknesses": "Pros: This paper shows a strong theoretical foundation that distinguishes this work from many others in the domain, through theoretical guarantees and carefully formulated proofs. The authors also provide comprehensive ablation studies that thoroughly demonstrate the effectiveness of individual components of the proposed method.\n\nCons: The manuscript lacks explicit discussion comparing the proposed curriculum-based masking framework with adversarial training methods, which are widely used in self-supervised learning. Such a comparison could offer valuable insights into alternative methodologies.  The experimental details especially dataset split is not clear.", "other_comments_or_suggestions": "The authors could enhance the manuscript by explicitly discussing the similarities and differences between their curriculum-based masking framework and adversarial training methods, which are common in self-supervised learning contexts. Such a discussion could provide valuable insights into alternative approaches for dealing with training difficulty in SSL. The authors could clarify the dataset split and whether the split follows the common practice in the literature.", "questions_for_authors": "How does the curriculum scheduling compare to adversarial training techniques in self-supervised learning? I am also curious that can the proposed method be extended to graph classification tasks in addition to the node and link classification tasks?", "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": "", "extra_scores": {}}, {"review_id": "N9ostAYkJY", "reviewer": "Reviewer_4EHD", "summary": "This paper studies self-supervised learning on graphs. The authors introduce an interesting strategy that structures the training of masked graph autoencoders in a progressive manner, allowing the model to learn more effective node representations for predictions. A key component of their approach is a difficulty-aware mechanism that evaluates the complexity of edges, enabling the design of more structured pretext tasks in SSL. By gradually increasing the complexity of masked edge reconstruction through a self-paced scheduler, the model ensures a more meaningful learning trajectory for the graph neural network. This methodology enhances the quality of learned node embeddings, leading to improved performance across various downstream tasks. The paper also presents a theoretical analysis of the proposed framework’s convergence properties and provides empirical evidence from multiple real-world datasets, demonstrating its effectiveness in node classification and link prediction tasks.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback. We addressed all the comments. Please kindly find the detailed responses to the comments below.\n\n**W1:** Motivation and how to set the hyperparameter $\\lambda$.\n\nThanks for your comment. We would like to clarify that $\\lambda$ is a coefficient to control the number of edges to be selected during the training process. A large $\\lambda$ encourages more edges to be selected for training (i.e., masking and reconstruction). Therefore, the motivation is that we can schedule the easy-to-hard training by increasing $\\lambda$ along with the iteration step $t$. At the beginning of the training process, a small portion of edges are masked and reconstructed with a small $\\lambda$ which is relatively easy for the GNNs. As iteration step $t$ increases, more edges are selected into the training process which makes it harder to be reconstructed. More specifically, we set $\\lambda$ as: $\\lambda = \\frac{\\lambda_{initial}}{T* \\lfloor \\frac{2}{3} \\rfloor+1-t}$ if $\\quad t < T* \\lfloor \\frac{2}{3} \\rfloor$ and $\\lambda = \\lambda_{initial}$ else, where $T$ is the total number of training epochs.\n\nWe will add more detailed analyses in the revised paper.\n\n\n\n**W2&Q1:** Analysis of the scalability of the method and training time.\n\nThank you for this comment. We would like to clarify that our method can scale to large graph considering its good time complexity. Specifically, we adopted the message-passing GNNs whose time complexity is $O(Ed+Nd^2)$, where $N$ and $E$ represent the total number of nodes and edges in the graph, and $d$ is the representation’s dimensionality. The time complexity of the decoder and the self-paced mask scheduler are both $O(Ed)$, because we calculate the residual error for each edge. Instead of all $N\\times N$ potential edges, only existing edges of the input graph are considered to be selected. Therefore, the time complexity of the complexity-guided curriculum masking is $O(E)$.  For this reason, the overall time complexity of our model is $O(Ed+Nd^2)$, which is on par with that of other GNN-based graph representation methods, which is also $O(Ed+Nd^2)$, demonstrating good scalability to large graphs. Empirically, we also tested our model on large graphs, e.g., OGBN-arxiv, which has 169,343 nodes and 1,166,243 edges, and OGBL-ppa, which has 576,289 nodes and 30,326,273 edges. The following table reports the training time per epoch, which is acceptable and also comparable with the baseline S2GAE. (LP: link prediction; NC: node classification).\n\n|          | LP          | LP          | LP           | NC          | NC          | NC          |\n| -------- | ----------- | ----------- | ------------ | ----------- | ----------- | ----------- |\n|          | Cora        | Citeseer    | OGBL-ppa     | Cora        | Citeseer    | OGBN-arxiv  |\n| Cur-MGAE | 0.045±0.003 | 0.043±0.004 | 79.117±1.753 | 0.093±0.020 | 0.089±0.015 | 1.718±0.593 |\n| S2GAE    | 0.048±0.008 | 0.045±0.009 | 77.469±1.224 | 0.100±0.020 | 0.098±0.009 | 2.600±0.357 |\n\n\n\n**Q2:** How to evaluate the difficulty levels of masking edges? \n\nThanks for the question. Our model selects easily learned edges for masking at the earlier stages of training and gradually incorporates more difficult edges as training progresses. To achieve this, we introduce a parameter $\\lambda$, which increases over iterations, acting as a regularizer for determining which edges to select. During training, the difficulty of each edge is quantified by the **residual** between the original graph and the predicted graph, calculated as $\\mathbf{R} = \\mathbf{A} - \\mathbf{A}\\_{re}$, where $\\mathbf{A}$ is the original adjacency matrix and $\\mathbf{A}_{re}$ is the reconstructed adjacency matrix. **Edges with smaller residuals are considered easier to predict and are masked earlier**, while those with larger residuals are gradually introduced as the model becomes more robust. This approach aligns well with curriculum learning strategies where the model starts with easier tasks and progressively tackles harder ones. The residual error effectively reflects how well the current model can predict a given edge. A smaller residual indicates that the model has learned to accurately reconstruct that edge, suggesting it is appropriate to mask it early on, while larger residuals imply greater difficulty. And we employ a self-paced mask scheduler. This scheduler incrementally increases the number of masked edges during training by introducing a relaxation of the edge selection process. Note that this design is inspired by the **human curriculum learning strategies** that can help the model training process.  \n\nWe will add the detailed discussion and references in the revised paper.", "claims_and_evidence": "The claims presented in the paper are supported by theoretical analysis and empirical results. The authors provide clear quantitative comparisons in tables and figures, demonstrating the advantages of their method over existing SSL approaches. The results for node classification show that Cur-MGAE achieves higher accuracy than competing methods across six benchmark datasets, indicating its effectiveness in capturing meaningful representations. The link prediction results show the model’s ability to reconstruct graph structures more effectively, particularly on large-scale datasets. The visualizations of edge selection strategies provide qualitative evidence that the proposed difficulty-aware mechanism successfully prioritizes easy-to-hard learning.", "methods_and_evaluation_criteria": "The methodology is solid and well-explained. The evaluation strategy is fair. However, the authors should consider comparing the efficiency with the baselines, since relatively complex techniques are introduced in the method design.", "theoretical_claims": "The paper provides rigorous theoretical analysis to support the rationale of the model. Specifically, the authors prove the avoidance of saddle points, ensuring that the model does not get stuck in suboptimal local minima, and the second-order convergence properties, demonstrating the stability of the optimization process.", "experimental_designs_or_analyses": "The experimental design is convincing, which includes a broad selection of datasets, covering different graph domains and sizes, and comprehensive baseline comparisons, including both contrastive and generative graph SSL approaches. Most importantly, the ablation studies demonstrate the necessity of key components, such as the curriculum-based masking and the cross-correlation decoder.", "relation_to_broader_scientific_literature": "The key contributions of the paper are related to the broader scientific literature on curriculum learning.", "essential_references_not_discussed": "I do not think there are essential references that are not discussed.", "other_strengths_and_weaknesses": "Generally, I think it is a novel approach to graph SSL community. The idea of combining curriculum learning with masked graph autoencoders is valuable. The proposed method consistently outperforms state-of-the-art approaches in node classification and link prediction. The paper provides formal proofs of convergence, enhancing the theoretical soundness of the approach. The explanation of complexity-guided curriculum masking and self-paced scheduling is intuitive and well-structured. \nThe other weakness lies in the limited analysis of the efficiency of the method. It is unclear whether the method adds computational complexity because of the difficulty-aware edge selection and scheduling mechanisms. And it is also unclear why the authors set $\\lambda$ to its specific value in Equation 7.", "other_comments_or_suggestions": "Since the hyperparameter $\\lambda$ plays a key role in the method, it is necessary to explain the motivations behind setting its value. Besides, the authors should analyze the scalability issue of the method.", "questions_for_authors": "I have some questions for the authors:  1) Is the training time acceptable for your method? 2) What criteria did you use to evaluate the difficulty levels of masking edges? Could you elaborate on the methodology behind this design? Is there any evidence in the literature that supports this design?", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes a curriculum-based self-supervised masked graph autoencoder to consider the degrees of difficulty of recovering the masked edges. It designs a structure-aware measurement to identify the degree of difficulty and adopts a self-paced strategy to determine the order of masking edges. Evaluations demonstrate the superiority of our proposed method. The claims are supported by clear and convincing evidence. The proposed method makes sense. All reviewers believe the proposed method is novel in graph SSL and the theoretical analysis is rigorous. All of them agree to accept this paper.
Decision: Accept (spotlight poster)