StructComp: Substituting propagation with Structural Compression in Training Graph Contrastive Learning

Q7:Why not comparing efficient GCL baselines such as CCA-SSG, and GGD discussed in the paper?

We have compared the performance of CCA-SSG with CCA-SSG trained using StructComp in the experimental section of the original submission. The specific results can be found in table 1 and table 2 of section 6. Clearly, the performance of CCA-SSG trained with StructComp far surpasses the original CCA-SSG. Moreover, we add a comparison between StructComp and GGD in the new submission, the specific results are shown in the table below. The performance and resource consumption of various GCL models trained with StructComp are superior to GGD.

Table 6: The results of StructComp-trained GCLs and GGD.

Q8:How the time and memory cost are computed? Do they count in the preprocessing steps?

We compute the time and memory cost in the same way as previous work on scalable GNNs: the time is the training time per epoch and memory is the peak GPU memory cost during training. The preprocessing time for our StructComp is strictly less than common scalable methods (e.g., ClusterGCN, GraphSaint and GraphAutoScale), since it only performs METIS once (like ClusterGCN) and does not need to do random sampling in each epoch. METIS is highly scalable and even papers100M (with 100M nodes) can be processed within an hour on a commercial CPU. Thus for big graphs, the prepocessing time is dominated by the training time, and more importantly, it only needs to be done once and the partition result can be shared by all experiments.

---

The discussion of all the aforementioned issues will be added into the revised version of our paper. We appreciate your insightful feedback once again.

[1]H. Zhu, and P. Koniusz. Simple spectral graph convolution. ICLR 2020.

[2]H. Zhu, and P. Koniusz. Generalized Laplacian Eigenmaps. Neurips 2022.

[3]Fang, T., Xiao, Z., Wang, C., Xu, J., Yang, X., and Yang, Y. Dropmessage: Unifying random dropping for graph neural networks. AAAI 2023.

Q3: How well can StructComp approximate different augmentations in GCL?

For multi-view GCLs, we designed a new data augmentation method, Dropmember, for our StructComp. It is important to note that Dropmember is not designed to approximate other graph data augmentation methods, but rather because previous graph data augmentation methods cannot be used under the StructComp framework. According to the analysis in DropMessage [3], common graph data augmentations can be unified under a single framework, and we have proved that our Dropmember falls within this framework as well.

Q4:The paper claims that StructComp can work for large scale graphs, while the benchmarked datasets are rather small or medium scale. Although it’s claimed that ogbn-products and arxiv are large datasets, while they are indeed medium scale datasets according to OGB. To support the claim, it’s expected to evaluate StructComp in large datasets such as papers100M, reddit, or OGBG-LSC datasets.

We have conducted extra experiments on the ogbn-papers100M dataset according to your suggestion. We use StructComp to train four representative GCL models. Here, we compressed ogbn-papers100M into a feature matrix $X_c \in R^{5000*128}$ and trained GCL using StructComp. The table also presents the results of GGD trained with ClusterGCN. Although GGD is specifically designed for training large graphs, when dealing with datasets of the scale of ogbn-papers100M, it still requires graph sampling to construct subgraphs and train GGD on a large number of subgraphs. In contrast, our StructComp only requires training a simple and small-scale MLP, resulting in significantly lower resource consumption compared to GGD+ClusterGCN.

Table 3: The accuracy, training time per epoch and memory usage on the Ogbn-papers100M dataset.

Q5:The paper also claims that StructComp has better robustness and stability with the additional regularization, while no evidence’s been found.

We have conducted extra experiments to study the robustness of StructComp. We randomly add 10% of noisy edges into three datasets and perform the node classification task. On the original dataset, the models trained with StructComp showed performance improvements of 0.36, 0.40, 1.30 and 1.87, respectively, compared to the models trained with full graphs. With noisy perturbation, the models trained with StructComp showed performance improvements of 0.80, 1.27, 2.47, and 1.87, respectively, compared to full graph training. This indicates that GCL models trained with StructComp exhibit better robustness.

Table 4: The results over 50 random splits on the perturbed datasets.

Thank you for your detailed review. We would like to address your questions/concerns below:

Q1:Theoretically, StructComp has to rely on the approximation of the diffusion matrix for a specific graph and GNN model, as demonstrated in Theorem 4.1. How well StructComp can approximate to more complicated graphs such as heterophilous graphs, and more complicated while commonly used GNNs such as GraphSage, GIN, GAT, or even more interesting variants such as PNA?

In order to verify the approximation quality to the diffusion matrix of StructComp, we test the performance on a deep GNN architecture called SSGC [1]. We transferred the trained parameters of StructComp to the SSGC encoder for inference. For full graph training in GCL, both the training and inference stages were performed using the SSGC encoder. Table 1 shows our experimental results, indicating that even with a deeper and more complicated encoder, StructComp still achieved outstanding performance.

Table 1: The results of GCLs with SSGC encoders over 50 random splits.

To the best of our knowledge, current mainstream GCL models, whether single-view models such as SCE, COLES, GLEN [2], or multi-view models such as DGI, GRACE, CCA-SSG, GGD, and their variants, all use SGC or GCN encoders. These unsupervised GCL models can achieve performance surpassing supervised GNNs (such as GAT, SAGE) with simple encoders on many datasets. Few GCL models have focused on whether using different encoders can achieve better performance. Moreover, GCL training is more complicated than supervised GNNs, so introducing complex encoders may make the models more difficult to train. Considering this, we did not extensively explore how using other encoders would affect StructComp. We believe this is a good question, and we will investigate it further in future work.

On the other hand, we have not implemented StructComp on heterophilous graphs , as the chosen basic GCL methods - SCE, COLES, GRACE, and CCA-SSG - are not suitable for heterophilous graph. In our future work, we will explore applying StructComp to more complex graph data structures.

Q2:Empirically, what is the exact setting of StructComp for node classification? Can StructComp be applied to both transductive and inductive node classification?

Our StructComp can also be used to handle inductive node classification tasks. We provide additional experiments on inductive node classification in Table 2. Clearly, the GCL models trained with StructComp also perform exceptionally well on inductive node classification tasks.

Table 2: The results on two inductive datasets. OOM means Out of Memory on GPU.

Q6:Some GCL works have not been discussed in the paper, for example, [1,2,3].

It should be noted that the goal of these studies and our work are different. The aim of SPGCL is to handle homophilic graphs and heterophilic graphs simultaneously. BlockGCL attempts to explore the application of deep GNN encoder in the GCL field. Contrast-Reg is a novel regularization method which is motivated by the analysis of expected calibration error. On the other hand, StructComp is a framework designed to scale up the training of GCL models: it aims to efficiently train common GCL models without performance drop. It is not a new GCL model that aims to achieve SOTA performance compared to existing GCL models. So our work is orthogonal to these three previous works. In fact, StructComp can be used as the training method for SP-GCL, BlockGCL and Contrast-Reg. In future work, we will further investigate how to train these recent graph contrastive learning methods using StructComp.

In terms of scalability, which is the main goal of our work, we have conducted extra experiments to compare SP-GCL, BlockGCL, Contrast-Reg and StructComp-trained baseline. The results confirm that the aforementioned three GCL models are not designed for reducing training costs.

Table 5: The results of StructComp-trained GCLs and some GCL baselines over 50 random splits. For SP-GCL, we are unable to get the classification accuracy on CiteSeer since it does not take isolated nodes as input.

Dear Reviewer kF3D,

We thank you again for your insightful and constructive review. We have worked hard and have thoroughly addressed your comments in the rebuttal.

As the discussion period soon comes to an end, we are looking forward to your feedback to our response and revised manuscript. Many thanks again for your time and efforts.

Best regards,

Authors of Submission 5510

As the scale of the graph dataset increases, all GCL models need to use graph sampling or graph partitioning techniques to construct subgraphs and then train GCL on subgraphs. Therefore, pre-processing like METIS is necessary, there are no issue where pre-processing increases the overall time. In our StructComp, METIS only needs to be performed once. Then, we can use the results of the graph partitioning to train various GCL models. Tables 3 and 4 in the original submission have already proven that StructComp has achieved the best trade-off between performance and efficiency on large graphs. To further illustrate this point, we provide the overall time results on 100M.

Table 10. The overall time and memory usage on the Ogbn-papers100M dataset.

Regarding the overhead for inference. Firstly, the overhead for inference is the same whether or not StructComp is used. The overhead for inference is solely related to the specific encoder used. Secondly, our work is only focused on the training process, as it is the most resource-intensive part of the entire pipeline. In contrast, inference is much simpler compared to training, and there are already straightforward and effective methods available for accelerating inference with GNN encoders [1,2]. For the 100M dataset, we utilized these methods to speed up the inference process. In our experiments, we utilized the same encoder for each dataset. The corresponding inference overheads are displayed in Table 11.

Table 11. The overhead for inference. Due to the large size of 100M, we employed neighbor sampling during the inference process. For all other datasets, we performed full graph inference.

[1] 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. Neurips 2020.

[2] Gasteiger, J., Qian, C. and Günnemann, S. Influence-based mini-batching for graph neural networks. LOG 2022.

Thank you for your feedback . We would like to address your questions/concerns below:

Regarding Q1: Since the heterophilous graphs have received lots of attention from the community, it'd be better if StructComp could be implemented for both kinds of graphs, with the suitable GCL method such as SP-GCL.

We provide experiments of training SP-GCL with StructComp to verify the performance of StructComp on heterophilous graphs. The experimental results are shown in Table 7. Overall, the SP-GCL trained by StructComp is superior to full graph training. This is our initial attempt to use StructComp to handle heterophilous graphs, and it is obviously a valuable direction worth further research.

Table 7. The results on heterophilous datasets.

Regarding Q8: In practice, the pre-processing time must be considered to find the best trade-off in terms of performance and efficiency, considering different scales of the graphs (the small, medium scale graphs in the original submission; and the large-scale graphs presented in the authors' response). It's important to present the efficiency results including the full pipeline of different methods, i.e., the overall time/mem cost for training the model, and the overhead for inference.

As we said in our previous response, the pre-processing of our StructComp only needs to perform METIS once. The specific time for METIS on our CPU is shown in Table 8.

Table 8. Preprocessing time.

For small and medium datasets, the time required by METIS is very short. Therefore, in these basic GCL models, the overall time required for full graph training is still more than that of StructComp. The results are shown in Table 9.

Table 9. The overall time (seconds) and memory usage (MB) on small and medium datasets.

Q2:Inadequate theoretical provements: The theoretical justifications provided are somewhat limited.

We understand your concern that the ER model may seem a strong assumption and possibly not entirely reflective of real-world scenarios. However, random graphs like the ER graph and the CSBM is widely adopted for GNN analysis(e.g., [3-8]). In our paper, we choose ER over CSBM since they have no significant difference in unsupervised GCL. We will specify the data distribution we used for analysis in the abstract and introduction. We would also like to point out that strong assumptions are common in the analysis of neural networks, e.g., infinite width in NTK [9], shallow layers [10], removing non-linearity [11], and strong data distribution assumptions [3-8].

According to the suggestion of the reviewer, we give an extra analysis on arbitrary graphs. For non-random graphs, the approximation gap of losses is simply bounded by the Eq 4. Suppose the loss $\mathcal{L}$ is $L$-Lipschitz continuous,

$

\begin{split}
    |\mathcal{L}(P^\dagger P^TXW)-\mathcal{L}(\hat{A}^kXW)|\leq L \underbrace{\Vert P^\dagger P^T - \hat{A}^k\Vert}_\text{Eq 4.}  \Vert X\Vert  \Vert  W\Vert .
\end{split}

$

And for a spectral contrastive loss $\mathcal{L}'$ , assume the graph partition are even, we have:

$

\mathcal{L}'(P^TXW)=-\frac{2}{n}\sum_{i=1}^n e^T_{1,i}e_{2,i}+\frac{1}{n^2}\sum_{i=1}^n \sum_{j=1}^n (e^T_{1,i} e_{2,j})^2 =-\frac{2}{n}\sum_{k=1}^{n'}\sum_{i\in S_k}e^T_{1,i}e_{2,i}+\frac{1}{n^2}\sum_{i=1}^n \sum_{l=1}^{n'} \sum_{j\in S_l} (e^T_{1,i} e_{2,j})^2

$

$

    =-\frac{2}{n'}\sum_{k=1}^{n'}E^T_{1,i}E_{2,i}+\frac{1}{nn'}\sum_{i=1}^n \sum_{l=1}^{n'}  (e^T_{1,i} E_{2,j})^2
    =-\frac{2}{n'}\sum_{k=1}^{n'}E^T_{1,i}E_{2,i}+\frac{1}{nn'}\sum_{k=1}^{n'}\sum_{i\in S_k} \sum_{l=1}^{n'}  (e^T_{1,i} E_{2,j})^2

$

$

    =-\frac{2}{n'}\sum_{k=1}^{n'}E^T_{1,i}E_{2,i}+\frac{1}{n'^2}\sum_{k=1}^{n'}\sum_{l=1}^{n'}  (E^T_{1,i} E_{2,j})^2=\mathcal{L}'(P^\dagger P^TXW),

$

where $e_{1,i}$ denotes the representations of a recovered node and $E^T_{1,i}$ denotes the representations of a compressed node. The above analysis shows that our approximation is reasonable for fixed graphs.

Empirically, we want to highlight Figure 3 in the original submission as it greatly validates our approximation on real-world datasets. We have trained two encoders $U$ and $W$ with the compressed loss $\mathcal{L}(X_c; U)$ and the original loss $\mathcal{L}(A,X;W)$, respectively. And we plot the trends of the origianl loss on $U$ and $W$ (i.e., $\mathcal{L}(A,X;U)$ and $\mathcal{L}(A,X;W)$). The figure clearly shows that vanilla training method and StructComp yields extremely similar trends, which justifies our approximation.

Q3:Lack of the discussion about the limitations.

Thank you for your feedback. We will provide a detailed discussion of the limitations of StructComp in the revised version. To our knowledge, StructComp is the first training framework specifically designed for GCL models, focusing only on basic and common GCL models. Our future work will involve generalizing StructComp to more complex GCL models, graph data structures.

The discussion of all the aforementioned issues will be added into the revised version of our paper. We appreciate your insightful feedback once again.

[1]Chiang, W. L., Liu, X., Si, S., Li, Y., Bengio, S., & Hsieh, C. J. Cluster-gcn: An efficient algorithm for training deep and large graph convolutional networks. KDD 2019.

[2]Fey, M., Lenssen, J. E., Weichert, F., & Leskovec, J. Gnnautoscale: Scalable and expressive graph neural networks via historical embeddings. ICML 2021

[3]Wei, R., Yin, H., Jia, J., Benson, A. R., & Li, P. Understanding non-linearity in graph neural networks from the bayesian-inference perspective. Neurips 2022.

[4]Wu, X., Chen, Z., Wang, W. W., & Jadbabaie, A. A Non-Asymptotic Analysis of Oversmoothing in Graph Neural Networks. ICLR 2023.

[5]Su, J., Zou, D., Zhang, Z., & Wu, C. Towards Robust Graph Incremental Learning on Evolving Graphs. ICML 2023.

[6]Keriven, N., Bietti, A., & Vaiter, S. Convergence and stability of graph convolutional networks on large random graphs. Neurips 2020.

[7]Keriven, N., Bietti, A., & Vaiter, S. On the universality of graph neural networks on large random graphs. Neurips 2021.

[8]Keriven, N. Not too little, not too much: a theoretical analysis of graph (over) smoothing. Neurips 2022.

[9]Jacot, A., Gabriel, F., & Hongler, C. Neural tangent kernel: Convergence and generalization in neural networks. Neurips 2018.

[10]Hsu, D., Sanford, C. H., Servedio, R., & Vlatakis-Gkaragkounis, E. V. On the approximation power of two-layer networks of random relus. COLT 2021.

[11]Awasthi, P., Das, A., & Gollapudi, S. A convergence analysis of gradient descent on graph neural networks. Neurips 2021.

Thank you for your comments! Below are our responses.

Q1:Lack of discussion of graph partition.

Our main contribution is a novel scalable framework for training GCLs and empirically show that even with off-the-shelf partition algorithms, our framework achieves remarkable speedup. We believe that no need for a specially designed partition algorithm is actually a big advantage.

We agree that different graph partition algorithms will have an impact on the performance of StructComp. We have conducted extra experiments on graph partition. In Table 1, we demonstrate the effects of three algorithms, algebraic JC, variation neighborhoods, and affinity GS, on the performance of StructComp. These three graph coarsening algorithms are widely used in scalable GNNs, from which we can obtain the specific graph partition matrix P. The experimental results suggest that different graph partition methods has little impact on StructComp on these datasets.

Table 1: The results of different graph partition methods.

Graph partition is a common technique for scalable supervised GNN (e.g., ClusterGCN[1], GAS[2]), thus we have not introduced its details in our paper. To our knowledge, Metis is the mainstream graph partitioning method for scalable supervised GNNs. Previous work has not deeply investigated the impact of graph partitioning methods on scalable GNNs. We believe that this is a valuable research topic and we notice that there is an active submission at ICLR 2024 regarding this issue on scalable supervised GNNs .

Dear Reviewer iDuQ,

We thank you again for your insightful and constructive review. We have worked hard and have thoroughly addressed your comments in the rebuttal.

As the discussion period soon comes to an end, we are looking forward to your feedback to our response and revised manuscript. Many thanks again for your time and efforts.

Best regards,

Authors of Submission 5510

Dear Reviewer iDuQ,

The rebuttal phase ends today and we have not yet received feedback from you. We believe that we have addressed all of your previous concerns. We would really appreciate that if you could check our response and updated paper.

Looking forward to hearing back from you.

Best Regards,

Authors

Thank you for your detailed review. We would like to address your questions/concerns below:

Q1: How theoretical results could be generalized to non-linear models?

Thanks for the insightful question. We explain how to extend the results to non-linear deep models below.

Eq. (4) provides the motivation of structural compression on a linear GNN (which can also be considered as an approximation to one layer in a multi-layer non-linear GNN). The analysis can be extended to non-linear deep GNNs. For instance, given a two-layer non-linear GCN $\sigma(\\hat{A}\sigma(\\hat{A}XW_1)W_2)$, we first approximate $\hat{A}$ by P^† P^T, then the whole GCN can be approximated as

$ \sigma(P^† P^T\sigma(P^† P^TXW_1)W_2)&=\sigma(P^† P^TP^†\sigma(P^TXW_1)W_2)\\ &=P^†\sigma(\sigma(P^TXW_1)W_2). $

The first equality holds because P^† is a partition matrix and the last equality follows from the fact that P^TP^† = I. Therefore, our analysis provides theoretical justifications of using StructComp as a substitute for non-linear deep GNNs. We will add this extended analysis to the revision. Note that previous studies on scalable methods for training GNNs, such as GraphSaint [1], FastGCN [2], Adapt [3], GRADE [4] also rely on various types of approximation to the propagation matrix, however, their analyses only focus on the approximation quality to a single layer or only work for linear GNNs. On the contrary, our analysis of StructComp can be easily extended to non-linear deep GNNs, which is another advantage of our framework.

Q2:Experiment datasets are too small (even arxiv dataset is small)... please try some large-scale graph datasets (e.g., Yelp, Reddit datasets that previously GraphSaint paper) to validate the effectiveness.

The ogbn-products dataset used in our experiments has 2,449,029 nodes, which is much larger than both Yelp and Reddit you suggested. We have also conducted extra experiments on Flickr and Reddit to show the performance of StructComp under inductive setting. The experimental results are as follows. StructComp shows remarkable scalability on these datasets.

Table 1: The results on two inductive datasets. OOM means Out of Memory on GPU.

According to the suggestions of other reviewers, the experiments on the ogbn-papers100M (which has 111,059,956 nodes) are conducted as well. The experimental results are shown in Table 2. Here, we compressed ogbn-papers100M into a feature matrix $X_c \in R^{5000*128}$ and trained GCL using StructComp. Table 2 also presents the results of GGD trained with ClusterGCN. Although GGD is specifically designed for training large graphs, when dealing with datasets of the scale of ogbn-papers100M, it still requires graph sampling to construct subgraphs and train GGD on a large number of subgraphs. In contrast, our StructComp only requires training a simple and small-scale MLP, resulting in significantly lower resource consumption compared to GGD+ClusterGCN.

Table 2: The accuracy, training time per epoch and memory usage on the Ogbn-papers100M dataset.

Q3:Repeat experiment multiple times instead of just once. For example Figure 4.

We emphasize that all of the experiments in the original submission are results of multiple repetitions. On Cora, Citeseer, PubMed, Computers, and Photo, we repeated the experiment 50 times. On Arxiv and Products, we repeated the experiment 5 times. Figure 4 shows the average accuracy of 50 repetitions.

Q4:Does the proposed method work for graphs with multiple node/edge types?

Currently, we have not implemented StructComp on graphs with multiple node/edge types, as the chosen basic GCL methods - SCE, COLES, GRACE, and CCA-SSG - are not suitable for these types of graph data. In our future work, we will explore applying StructComp to more complex graph data structures.

---

The discussion of all the aforementioned issues will be added into the revised version of our paper. We appreciate your insightful feedback once again.

[1] H. Zeng, H. Zhou, A. Srivastava, R. Kannan, and V. K. Prasanna. Graphsaint: Graph sampling based inductive learning method. ICLR 2020.

[2] J. Chen, T. Ma, an C. Xiao. Fastgcn: fast learning with graph convolutional networks via importance sampling. ICLR 2018.

[3] W. Huang, T. Zhang, Y. Rong, and J. uang. Adaptive sampling towards fast graph representation learning. NIPS 2018.

[4] R Wang, X Wang, C Shi, L Song. Uncovering the Structural Fairness in Graph Contrastive Learning. Neurips 2022.

Dear Reviewer v4Cz,

We thank you again for your insightful and constructive review. We have worked hard and have thoroughly addressed your comments in the rebuttal.

As the discussion period soon comes to an end, we are looking forward to your feedback to our response and revised manuscript. Many thanks again for your time and efforts.

Best regards,

Authors of Submission 5510

According to the suggestion from reviewer kF3D, we have conducted experiments to train SP-GCL with StructComp, in order to verify the performance of StructComp on heterophilous graphs. The experimental results are shown in Table 3. Overall, the SP-GCL trained by StructComp is superior to full graph training. This is our initial attempt to use StructComp to handle heterophilous graphs, and it is obviously a valuable direction worth further research.

Table 3. The results on heterophilous datasets.

Dear Reviewer v4Cz,

The rebuttal phase ends today and we have not yet received feedback from you. We believe that we have addressed all of your previous concerns. We would really appreciate that if you could check our response and updated paper.

Looking forward to hearing back from you.

Best Regards,

Authors

Q4:There is a lack of comparisons with certain related works, such as recent graph contrastive learning methods [1-2].

It should be noted that the goal of these studies and our work are different. The aim of SPGCL is to handle homophilic graphs and heterophilic graphs simultaneously. BlockGCL attempts to explore the application of deep GNN encoder in the GCL field. On the other hand, StructComp is a framework designed to scale up the training of GCL models: it aims to efficiently train common GCL models without performance drop. It is not a new GCL model that aims to achieve SOTA performance compared to existing GCL models. So our work is orthogonal to these two previous works. In fact, StructComp can be used as the training method for both SP-GCL and BlockGCL. In future work, we will further investigate how to train these recent graph contrastive learning methods using StructComp.

In terms of scalability, which is the main goal of our work, we have conducted extra experiments to compare SP-GCL, BlockGCL and StructComp-trained baseline. The results confirm that the aforementioned two GCL models are not designed for reducing training costs.

Table 4: The results of StructComp-trained GCLs and some GCL baselines over 50 random splits. For SP-GCL, we are unable to get the classification accuracy on CiteSeer since it does not take isolated nodes as input.

---

The discussion of all the aforementioned issues will be added into the revised version of our paper. We appreciate your insightful feedback once again.

[1]H. Zhu, and P. Koniusz. Simple spectral graph convolution. ICLR 2020.

[2]H. Zhu, and P. Koniusz. Generalized Laplacian Eigenmaps. Neurips 2022.

Thank you for your detailed review. We would like to address your questions/concerns below:

Q1:Evaluating on larger datasets like papers100M and or OGBG-LSC datasets would better support scalability claims, since the experimented datasets are rather small or medium scale.

We have conducted extra experiments on the ogbn-papers100M dataset according to your suggestion. We use StructComp to train four representative GCL models. Here, we compressed ogbn-papers100M into a feature matrix $X_c \in R^{5000*128}$ and trained GCL using StructComp. The table also presents the results of GGD trained with ClusterGCN. Although GGD is specifically designed for training large graphs, when dealing with datasets of the scale of ogbn-papers100M, it still requires graph sampling to construct subgraphs and train GGD on a large number of subgraphs. In contrast, our StructComp only requires training a simple and small-scale MLP, resulting in significantly lower resource consumption compared to GGD+ClusterGCN.

Table 1: The accuracy, training time per epoch and memory usage on the Ogbn-papers100M dataset.

Q2:Would be great to verify the model stability/robustness with the proposed regularization, since it is claimed in the presentation.

We have conducted extra experiments to study the robustness of StructComp. We randomly add 10% of noisy edges into three datasets and perform the node classification task. On the original dataset, the models trained with StructComp showed performance improvements of 0.36, 0.40, 1.30 and 1.87, respectively, compared to the models trained with full graphs. With noisy perturbation, the models trained with StructComp showed performance improvements of 0.80, 1.27, 2.47, and 1.87, respectively, compared to full graph training. This indicates that GCL models trained with StructComp exhibit better robustness.

Table 2: The results over 50 random splits on the perturbed datasets.

Q3:Would be great to discuss the approximation quality to the diffusion matrix of StructComp for more complicated graphs and other models architectures (like GAT, GraphSAGE).

In order to verify the approximation quality to the diffusion matrix of StructComp, we test the performance on a deep GNN architecture called SSGC [1]. We transferred the trained parameters of StructComp to the SSGC encoder for inference. For full graph training in GCL, both the training and inference stages were performed using the SSGC encoder. Table 3 shows our experimental results, indicating that even with a deeper and more complicated encoder, StructComp still achieved outstanding performance. To the best of our knowledge, current mainstream GCL models, whether single-view models such as SCE, COLES, GLEN [2], or multi-view models such as DGI, GRACE, CCA-SSG, GGD, and their variants, all use SGC or GCN encoders. These unsupervised GCL models can achieve performance surpassing supervised GNNs (such as GAT, SAGE) with simple encoders on many datasets. Few GCL models have focused on whether using different encoders can achieve better performance. Moreover, GCL training is more complicated than supervised GNNs, so introducing complex encoders may make the models more difficult to train. Considering this, we did not extensively explore how using other encoders would affect StructComp. We believe this is a good question, and we will investigate it further in future work.

Table 3: The results of GCLs with SSGC encoders over 50 random splits.

Dear Reviewer PXMh,

We thank you again for your insightful and constructive review. We have worked hard and have thoroughly addressed your comments in the rebuttal.

As the discussion period soon comes to an end, we are looking forward to your feedback to our response and revised manuscript. Many thanks again for your time and efforts.

Best regards,

Authors of Submission 5510

According to the suggestion from reviewer kF3D, we have conducted experiments to train SP-GCL with StructComp, in order to verify the performance of StructComp on heterophilous graphs. The experimental results are shown in Table 5. Overall, the SP-GCL trained by StructComp is superior to full graph training. This is our initial attempt to use StructComp to handle heterophilous graphs, and it is obviously a valuable direction worth further research.

Table 5. The results on heterophilous datasets.

Dear Reviewer PXMh,

The rebuttal phase ends today and we have not yet received feedback from you. We believe that we have addressed all of your previous concerns. We would really appreciate that if you could check our response and updated paper.

Looking forward to hearing back from you.

Best Regards,

Authors