Self-supervised Masked Graph Autoencoder via Structure-aware Curriculum

We are grateful for your valuable comments. Please find our responses to each point below.

• Q1. The motivation on edge complexity.

R1: Thanks for your comment. We would like to clarify the motivation more clearly as follows:

1. We focus on a novel and challenging problem, i.e., learning informative representations by designing easy-to-hard mask-reconstruction pretext tasks for masked graph autoencoder. To the best of our knowledge, this problem is not explored by the existing works due to the unique challenges of designing curriculum strategy into graph self-supervised learning.
2. Due to the non-Euclidean nature of graph data where nodes are interconnected with each other, most existing curriculum learning works cannot be directly applied to graphs. It also remains a new research direction and is more challenging to design structure-aware curriculum learning strategies.
3. We find that for training masked graph autoencoders, the residuals between adjacent values and reconstructed values well quantify the degree that the edges are expected for the GNN encoders at the current stage, where a smaller residual error means the sample should be selected for training at an earlier stage and vice versa. It well aligns with human curriculum learning strategies that can help the model training process [1-6]. Therefore, we propose a tailored difficulty measurer to identify the structural difficulty degree of edges during the masking step. For scheduling edges to be trained, we further propose a novel self-paced scheduler where the intractable discrete optimization of edge selection can be solved by the proposed constrained optimization problem with Lagrange multiplier and also balance exploration and exploitation for training. Such end-to-end model designs are non-trivial.
4. We analyze the convergence guarantees of our model. Besides, our model achieves overall performance gains on several synthetic and real-world benchmarks against various baselines. We believe these technical contributions are non-trivial and have potential impacts on the community.

• Q2. The definition of edge complexity

R2: Thank you for the question. We have followed your suggestion to add the formal definition to the edge difficulty in lines 256-257 in the revised paper as follows: “Edge difficulty is the difficulty score measuring how hard for the current model to predict the edge correctly”. We follow the idea of curriculum learning, which is also applied in [1-6], to measure the difficulties of each edge and study the edges from easy to hard. To quantify the difficulties of each edge in a given graph, we first use the current model to reconstruct the original graph: $\mathbf{A_{re}} = {\rm DEC}({\rm ENC}(\mathbf{H}, \mathbf{A}))$. The predicted structure $\mathbf{A_{re}}$ reflects the edges that are expected to be inherently drawn from the current model, where the edge probabilities can be viewed as the model’s confidence for the edge occurrence. Intuitively, lower edge confidence indicates that the edge is more complex to be reconstructed by the current model. So we propose to leverage structural complexity to estimate the difficulties of the edge for curriculum learning. Specifically, we calculate the residual errors as: $\mathbf{R} = \mathbf{A} - \mathbf{A_{re}}$. The residual errors measure the distance between the predicted structure and the original structure, which indicates how difficult the edges are for the current model. Consequently, a smaller residual error could be interpreted as an indication of a more pronounced significance of the edge existence. This implies that such edges are relatively easier to learn and comprehend within the context of the model.

We adopted the edge mask-reconstruction as the pretext task so that the definition of node complexity is out of the scope of this work. Nevertheless, we believe a similar idea can be extended on node which can be verified in future work.

References:

[1] Zhao et al., Reinforced curriculum learning on pre-trained neural machine translation models. AAAI, 2020.

[2] Chen et al., Curriculum disentangled recommendation with noisy multifeedback. NeurIPS, 2021.

[3] Li et al., Graph Neural Network with curriculum learning for imbalanced node classification. Neurocomputing, 2024.

[4] Zhang et al., Learning to solve travelling salesman problem with hardness-adaptive curriculum. AAAI, 2022.

[5] Wang et al., CurGraph: Curriculum Learning for Graph Classification. WWW, 2021.

[6] Lan et al., Curriculum multi-negative augmentation for debiased video grounding. AAAI, 2023.

We would greatly appreciate it if you could reconsider your evaluation if some concerns on motivations and the definition are addressed. Thank you!

Dear Reviewer i2s5,

Thank you for taking the time to review our paper.

As the discussion deadline is approaching, we are eager to hear your feedback on our rebuttal. We hope that our responses have addressed your concerns and would be happy to clarify any further questions.

Looking forward to your valuable input.

Best regards, Authors

We thank the reviewer for the insightful comments. Please find our responses to each point below.

• Q1. There is a gap in using the residual errors of GAE to measure the confidence of a Masked graph autoencoder.

R1: Thank you for this comment. We would like to clarify the motivation using the residual errors of GAE as the difficulty measurer is that at the beginning phase, we could not determine which edges should be masked, and the function of the difficulty measurer is to find such edges. For this reason, Masked graph autoencoder can't be applied at this stage. Specifically, to quantify the difficulties of each edge in a given graph, we first use the current model to reconstruct the original graph: $\mathbf{A_{re}} = {\rm DEC}({\rm ENC}(\mathbf{H}, \mathbf{A}))$. The predicted structure $\mathbf{A_{re}}$ reflects the edges that are expected to be inherently drawn from the current model, where the edge probabilities can be viewed as the model’s confidence for the edge occurrence. Intuitively, lower edge confidence indicates that the edge is more complex to be reconstructed by the current model. So we propose to leverage structural complexity to estimate the difficulties of the edge for curriculum learning. Specifically, we calculate the residual errors as: $\mathbf{R} = \mathbf{A} - \mathbf{A_{re}}$. The residual errors measure the differences between the predicted structure and the original structure, which indicate how difficult the edges are for the current model. Consequently, a smaller residual error could be interpreted as an indication of a more pronounced significance of the edge existence. This implies that such edges are relatively easier to learn and comprehend within the context of the model. We have revised the expression in lines 256-268 for better clarification in the revised paper.

• Q2. More related works need to be discussed, e.g., GraphMAE2, AUG-MAE, and Bandana

R2: Thank you for this suggestion. In our experiments, we compared with some representative baselines in the field. To further compare our method with more updated methods as you suggested, we have adopted 3 more recent methods, i.e., Bandana [1], GraphMAE2 [2], and AUG-MAE [3]. Note that Bandana [1] proposes a novel framework for masked graph autoencoder that utilizes non-discrete edge masks, referred to as "bandwidths". Unlike discrete masking, these bandwidths are sampled from a continuous and dispersive probability distribution, allowing for a more nuanced restriction of message propagation through each edge, which maintains the integrity of the graph's topology during training, ensuring that long-range information can flow unimpeded and enhancing the model's ability to learn fine-grained neighborhood structures. GraphMAE2 [2] is a self-supervised learning framework designed to enhance graph representation learning by increasing the model robustness. Compared with its predecessor GraphMAE [4], the multi-view random re-mask decoding and latent representation prediction modules are designed to help with noisy and indistinguishable input features. AUG-MAE [3] targets on node and graph classification tasks, introducing an easy-to-hard adversarial masking approach that generates challenging samples for the model to reconstruct. This strategy enhances the model's ability to align representations of similar nodes, leading to more accurate and robust embeddings. The experimental results are shown in the below table. We can observe that our Cur-MGAE consistently achieves the best performance compared with these additional baselines. Noted that “/” indicates that the current method can’t be directly used on the datasets that do not have node features, and GraphMAE2 and AUG-MAE are omitted in the link prediction task since they are node or graph classification methods.

We have added the above results in Table 1 and Table 2 in the revised paper.

• Q3. The number of parameters of the proposed model and the baselines.

R3: Thank you for this comment. Following your suggestion, we have first analyzed the space complexity of our method and baselines as follows. “Ours model adopts GCN and GraphSAGE as the backbone model, whose 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 $N$ is the number of nodes, $F$ is the feature dimension, $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 neighbors per node for aggregation. In addition to the GNN backbones, our model introduces a complexity-guided curriculum masking and self-paced mask scheduler, whose space complexity are both $O(E)$, which does not induce a higher complexity. Therefore, the space complexity of our proposed model is on par with the existing methods”

In addition, we empirically calculate the number of parameters of the proposed model and baseline models by setting the same embedding dimensionality, which is shown in the following table. Note that the parameters are calculated on the Cora dataset, with a hidden dimension of 128. For GraphMAE, the GAT it uses is set to have 4 heads.

We can observe that although relatively complex designs are introduced, our method still has a comparable number of parameters with the baseline methods. We have added the detailed results and discussion in lines 1068-1089 in the revised paper.

References:

[1] Zhao et al., Masked Graph Autoencoder with Non-discrete Bandwidths. WWW, 2024.

[2] Hou et al., GraphMAE2: A Decoding-Enhanced Masked Self-Supervised Graph Learner. WWW, 2023.

[3] Wang et al., Rethinking Graph Masked Autoencoders through Alignment and Uniformity. AAAI, 2024.

[4] Hou et al., GraphMAE: Self-Supervised Masked Graph Autoencoders. KDD, 2022.

We hope our response can effectively address your initial concerns regarding method design, related works, and complexity. We sincerely appreciate your reconsideration of our work in light of our explanations.

Dear Reviewer G9un,

Thank you for taking the time to review our paper.

As the discussion deadline is approaching, we are eager to hear your feedback on our rebuttal. We hope that our responses have addressed your concerns and would be happy to clarify any further questions.

Looking forward to your valuable input.

Best regards,

Authors

• Q6. Theoretical principles support the effectiveness of the curriculum-based approach

R6: Thank you for this question. We hope the response to Q3 might address your concern about the theoretical guarantees.

• Q7. How to determine the criteria for evaluating the difficulty levels of masking edges?

R7: We have revised the expressions for better clarification on how to determine the criteria for evaluating the difficulty levels of masking edges as follows “To quantify the difficulties of each edge in a given graph, we first use the current model to reconstruct the original graph: $\mathbf{A_{re}} = {\rm DEC}({\rm ENC}(\mathbf{H}, \mathbf{A}))$. The predicted structure $\mathbf{A_{re}}$ reflects the edges that are expected to be inherently drawn from the current model, where the edge probabilities can be viewed as the model’s confidence for the edge occurrence. Intuitively, lower edge confidence indicates that the edge is more complex to be reconstructed by the current model. So we propose to leverage structural complexity to estimate the hardness of the edge for curriculum learning”. Please refer to lines 256-268 in the revised paper for details.

Reference:

[1] Tan et al., S2GAE: Self-Supervised Graph Autoencoders Are Generalizable Learners with Graph Masking. WSDM, 2023.

[2] Li et al., What’s Behind the Mask: Understanding Masked Graph Modeling for Graph Autoencoders. KDD, 2023.

[3] Zhao et al., Masked Graph Autoencoder with Non-discrete Bandwidths. WWW, 2024.

[4] Hou et al., GraphMAE2: A Decoding-Enhanced Masked Self-Supervised Graph Learner. WWW, 2023.

[5] Wang et al., Rethinking Graph Masked Autoencoders through Alignment and Uniformity. AAAI, 2024.

[6] Hou et al., GraphMAE: Self-Supervised Masked Graph Autoencoders. KDD, 2022.

[7] Zhao et al., Reinforced curriculum learning on pre-trained neural machine translation models. AAAI, 2020.

[8] Chen et al., Curriculum disentangled recommendation with noisy multifeedback. NeurIPS, 2021.

[9] Li et al., Graph Neural Network with curriculum learning for imbalanced node classification. Neurocomputing, 2024.

[10] Zhang et al., Learning to solve travelling salesman problem with hardness-adaptive curriculum. AAAI, 2022.

[11] Wang et al., CurGraph: Curriculum Learning for Graph Classification. WWW, 2021.

[12] Lan et al., Curriculum multi-negative augmentation for debiased video grounding. AAAI, 2023.

We hope our response can effectively address your initial concerns on scalability, baselines, theories, and complexity. We sincerely appreciate your reconsideration of our work in light of our explanations. We would be glad to engage further if there are any additional points we may have missed. Thank you!

We have added the above results in Table 1 and Table 2 in the revised paper.

• Q3. The theoretical principles supporting why these defined levels in curriculum-based approach are beneficial compared to traditional methods?

R3: Thank you for this comment. We provided theoretical analyses for the convergence properties of our method, which is the main aspect to show the effectiveness of the curriculum-based approach following the literature [7-12] and supports our model design. Besides, we empirically verify that adopting curriculum learning strategies can achieve better experimental results.

• Q4. Complexity of Implementation

R4: Thank you for this comment. We would like to clarify that the curriculum learning strategies in self-supervised masked graph autoencoder are one of the main contributions of our method, which is able to capture and leverage the underlying degree of difficulties of data dependencies hidden in edges and design better mask-reconstruction pretext tasks for learning informative representations. Its effectiveness is verified in the node classification tasks (Table 1) and link prediction (Table 2) tasks. In addition, we analyzed the time and space complexity of our method is comparable with the baseline methods (in sections E and F in Appendix), which does not introduce a high complexity of implementation.

• Q5. More recent or competitive baselines.

R5: Thank you for the question. We followed the related works [1-3] to choose the GCN and GraphSage as our backbones for a fair comparison. Following your suggestion, 3 more recent baselines where GraphMAE2 and AUG-MAE use GAT as the default backbone in their original paper are compared. The results in Q2 show that our method still outperforms the baselines that use GAT as the backbone.

Thank you for your efforts and insightful comments. We have provided detailed responses to address each of your concerns below.

• Q1. The scalability concerns on the difficulty measurer and self-paced scheduler.

R1: Thank you for this question. We analyzed the time complexity of our method in section E in the Appendix. Following your suggestion, we would like to discuss in more detail on the scalability as follows. The time complexity of our model is on par with the baselines, i.e., $O(Ed+Nd^2)$, where $N$, $E$ denotes the total number of nodes and edges in the graphs, $d$ is the dimensionality of the representation. Specifically, the time complexity of the self-paced mask scheduler is $O(Ed)$, since we calculate the residual for each edge. The time complexity of the complexity-guided curriculum masking is $O(E)$ because only existing edges are considered to be selected instead of all $N\times N$ potential edges. In addition, we adopt message-passing GNN as the encoder whose time complexity is $O(Ed+Nd^2)$. Overall, the computational efficiency of our method is promising.

Besides the results of the empirical time comparisons in Table 7 in the Appendix, I also conducted experiments on larger graphs OGBN-arxiv and OGBL-ppa. The results are shown in the following table. Noted that we report the total training time of 3 repeats for the node classification task and 5 repeats for the link prediction task, which accord with the experimental setting in Table 7.

We can also observe the good efficiency of our method, although it consists of the designs of the edge masking and reconstruction. We have added the detailed discussions into section E in the Appendix. Please refer to the revised paper for more details.

• Q2. The baselines are insufficient.

R2. Thanks for the comment. In our experiments, we compared with some representative baselines in the field. We followed the well-established evaluation setting in the literature [1] which is using SVM as the downstream classifier to evaluate the quality of representations output by the baselines and our model. So the results of our method are different from the GLEM, GIANT, SimTeg, and the methods on the leaderboard because the evaluation setting is different. We also noticed that in the literature, these methods are also not considered as the baselines in the related works [1-6].

Nevertheless, we have followed your suggestions to add 3 more recent methods, i.e., Bandana [3], GraphMAE2 [4], and AUG-MAE [5]. Note that Bandana [1] proposes a novel framework for masked graph autoencoder that utilizes non-discrete edge masks, referred to as "bandwidths". Unlike discrete masking, these bandwidths are sampled from a continuous and dispersive probability distribution, allowing for a more nuanced restriction of message propagation through each edge, which maintains the integrity of the graph's topology during training, ensuring that long-range information can flow unimpeded and enhancing the model's ability to learn fine-grained neighborhood structures. GraphMAE2 [4] is a self-supervised learning framework designed to enhance graph representation learning by increasing the model robustness. Compared with its predecessor GraphMAE [6], the multi-view random re-mask decoding and latent representation prediction modules are designed to help with noisy and indistinguishable input features. AUG-MAE [5] targets on node and graph classification tasks, introducing an easy-to-hard adversarial masking approach that generates challenging samples for the model to reconstruct. This strategy enhances the model's ability to align representations of similar nodes, leading to more accurate and robust embeddings. The experimental results are shown in the below table. We can observe that our Cur-MGAE consistently achieves the best performance compared with these additional baselines. Noted that “/” indicates that the current method can’t be directly used on the datasets that do not have node features, and GraphMAE2 and AUG-MAE are omitted in the link prediction task since they are node or graph classification methods.

• Q3. More discussions on computational efficiency. Will the self-paced mask scheduler and iterative edge selection induce a higher computational cost?

R3: Thank you for this question. We would like to clarify that the time complexity of our model is on par with the baselines, i.e., $O(Ed+Nd^2)$, where $N$, $E$ denotes the total number of nodes and edges in the graphs, $d$ is the dimensionality of the representation. Specifically, the time complexity of the self-paced mask scheduler is $O(Ed)$, since we calculate the residual for each edge. The time complexity of the complexity-guided curriculum masking is $O(E)$ because only existing edges are considered to be selected instead of all $N\times N$ potential edges. In addition, we adopt message-passing GNN as the encoder whose time complexity is $O(Ed+Nd^2)$. Overall, the computational efficiency of our method is promising.

Besides the results of the empirical time comparisons in Table 7 in the Appendix, we have also conducted experiments on larger graphs OGBN-arxiv and OGBL-ppa. The results are shown in the following table. Noted that we report the total training time of 3 repeats for the node classification task and 5 repeats for the link prediction task, which accord with the experimental setting in Table 7.

We can also observe the good efficiency of our method. Please refer to the line 1023-1065 in the revised paper for more details.

Reference:

[1] Zhao et al., Masked Graph Autoencoder with Non-discrete Bandwidths. WWW, 2024.

[2] Hou et al., GraphMAE2: A Decoding-Enhanced Masked Self-Supervised Graph Learner. WWW, 2023.

[3] Wang et al., Rethinking Graph Masked Autoencoders through Alignment and Uniformity. AAAI, 2024.

[4] Hou et al., GraphMAE: Self-Supervised Masked Graph Autoencoders. KDD, 2022.

We sincerely appreciate your positive evaluation of our work and have conducted additional experiments based on your valuable suggestions. We would very much appreciate it if you could reconsider your evaluation if some concerns are addressed. Thank you very much!

We sincerely appreciate the reviewer for the valuable positive feedback. We addressed all the comments. Please kindly find the detailed responses below.

• Q1. Some typos in the paper.

R1: Thank you for the comment. We have followed your suggestion to add the reference for PubMed in lines 363 and 367, and revise the “citepseer” into “CiteSeer”.

• Q2. More recent baselines should be compared.

R2: Thank you for this suggestion. In our experiments, we compared with some representative baselines in the field. To further compare our method with more updated methods as you suggested, we have adopted 3 more recent methods, i.e., Bandana [1], GraphMAE2 [2], and AUG-MAE [3]. Note that Bandana [1] proposes a novel framework for masked graph autoencoder that utilizes non-discrete edge masks, referred to as "bandwidths". Unlike discrete masking, these bandwidths are sampled from a continuous and dispersive probability distribution, allowing for a more nuanced restriction of message propagation through each edge, which maintains the integrity of the graph's topology during training, ensuring that long-range information can flow unimpeded and enhancing the model's ability to learn fine-grained neighborhood structures. GraphMAE2 [2] is a self-supervised learning framework designed to enhance graph representation learning by increasing the model robustness. Compared with its predecessor GraphMAE [4], the multi-view random re-mask decoding and latent representation prediction modules are designed to help with noisy and indistinguishable input features. AUG-MAE [3] targets on node and graph classification tasks, introducing an easy-to-hard adversarial masking approach that generates challenging samples for the model to reconstruct. This strategy enhances the model's ability to align representations of similar nodes, leading to more accurate and robust embeddings. The new experimental results are shown in the table below. We can observe that our Cur-MGAE consistently achieves the best performance compared with these additional baselines. Noted that “/” indicates that the current method can’t be directly used on the datasets that do not have node features, and GraphMAE2 and AUG-MAE are omitted in the link prediction task since they are node or graph classification methods.

We have added the above results in Table 1 and Table 2 in the revised paper.

Dear Reviewer LL8M,

Thank you for taking the time to review our paper.

As the discussion deadline is approaching, we are eager to hear your feedback on our rebuttal. We hope that our responses have addressed your concerns and would be happy to clarify any further questions.

Looking forward to your valuable input.

Best regards,

Authors