Exploring Consistency in Graph Representations: from Graph Kernels to Graph Neural Networks

We appreciate the reviewer's insightful question regarding the extension of our method to graph clustering tasks and large-scale graph datasets, since complexity and scalability are significant concerns in practical applications.

1.On Graph Clustering Tasks.

While applying our consistency loss to the graph clustering task is an interesting idea, it's important to note that our method is specifically designed for graph-level tasks rather than node-level tasks. This approach is grounded in graph kernels, which are predominantly used for graph-level applications. Thus, there are no theoretical guarantees for node-level tasks. Furthermore, unlike graph classification tasks where similarities are computed only within a batch of graphs, applying this approach to clustering requires calculating similarities between all nodes within a graph, which significantly increases computational costs. Nevertheless, we manage to apply our consistency loss to the Attention-driven Graph Clustering Network (AGCN) model[1] on the ACM dataset by leveraging a sampling strategy to compute similarities among the nodes. Following previous research[1,2], we evaluate the quality of clustering using four key metrics: Accuracy (ACC), Normalized Mutual Information (NMI), Average Rand Index (ARI), and macro F1-score (F1). Higher values for each metric signify better clustering performance. The results, presented in Table R11, demonstrate that applying our method to a clustering model leads to slight improvements. This suggests that our approach has the potential to enhance performance in graph clustering tasks.

Table R11: Graph clustering on ACM Dataset, evaluated in terms of accuracy/NMI/ARI/F1.

2.On Large-Scale Datasets.

As described in our general response, the computational cost associated with our method scales linearly with the dataset size, which is small compared to the training time. Furthermore, we conduct additional experiments to run our model on a real-world large dataset, Reddit Threads dataset[3], which contains over 200,000 graphs. We present the results in Table R12.

Tabel R12. Graph classification performance on Reddit Threads dataset, measured in accuracy.

Table R12 demonstrates that our method remains effective on large datasets and achieves noticeable improvements across a range of backbone networks.

[1] Peng, Z., Liu, H., Jia, Y., & Hou, J. (2021). Attention-driven Graph Clustering Network. Proceedings of the 29th ACM International Conference on Multimedia.

[2]Bo, D., Wang, X., Shi, C., Zhu, M., Lu, E., & Cui, P. (2020). Structural Deep Clustering Network. Proceedings of The Web Conference 2020.

[3]Rozemberczki, B., Kiss, O., & Sarkar, R. (2020). An API Oriented Open-source Python Framework for Unsupervised Learning on Graphs. ArXiv, abs/2003.04819.

3.Typo.

We thank the reviewer for reminding us of this issue. We will address it in the next version.

We appreciate the reviewer's question about artificial experiments, which provides an opportunity to explore how this method performs across different data scenarios. Should there be any remaining issues or suggestions for improvement, we welcome further feedback on how to refine our approach.

1.Increasing label alphabet.

To investigate the influence of an increasing label alphabet on the runtime and performance of our method, we generated subsets with an increasing number of classes from the REDDIT-MULTI-5K dataset, which originally comprises five classes. Specifically, we randomly sampled between 2 to 4 classes from the dataset and run GCN and GCN+$\mathcal{L}_{\text{consistency}}$ on these subsets.

Table R7. Graph classification performance on subsets of REDDIT-MULTI-5K, measured in accuracy.

The results in Table R7 show that the effectiveness of our method remains unaffected by the growing number of labels.

We further measure the runtime of the models on these subsets and present the results in Table R8. As shown in Table R8, the addtional time costs do not change much with the growing number of labels.

Table R8: Average training time per epoch on subsets with varying class complexity from REDDIT, measured in seconds.

2.Increasing structural complexity.

We evaluate the impact of structural complexity by dividing the IMDB-BINARY dataset into three subsets with increasing graph density. This density, denoted as $d=\frac{2 m}{n(n-1)}$, where $n$ is the number of nodes and $m$ is the number of edges in graph $G$, was employed as the criterion for creating these subsets. Specifically, the datasets were divided into: (small) for graphs with a density below the 33rd percentile, (median) for densities between the 33rd and 67th percentiles, and (large) for graphs with a density above the 67th percentile. We run GCN and GCN +$\mathcal{L}_{\text{consistency}}$ models on these subsets and present the results in Table R9.

Table R9. Graph classification performance across subsets of varying structural complexity from IMDB-B. Performance is measured in accuracy.

Based on these results, we can conclude that with the $\mathcal{L}_{\text{consistency}}$ loss function, the GCN model consistently outperforms the original version across varying levels of structural complexity in both datasets, underscoring the effectiveness of the proposed method.

We also conducted experiments to assess the training costs on datasets with different structural complexities when introducing the $\mathcal{L}_{\text{consistency}}$ loss. The results are presented below.

Table R10. Average training time per epoch for subsets of varying structural complexity from IMDB-B, measured in seconds.

Given these results, we find that the additional training cost is minimal across datasets with different structural complexities, demonstrating its broad applicability.

For more analysis in time and space complexity of our method, please refer to the general responses.

3.Critical difference diagram.

While the suggestion to include critical difference diagrams is appreciated, these diagrams may not be suitable for our context. As shown in Table 1 and 2 (in the main paper), incorporating consistency loss generally enhances the performance of the baseline models. However, no clear ranking emerges across the different baselines, as each model excels in distinct datasets across various domains. Since the primary goal of this paper is not to determine the relative ranking of these models, such rankings would not yield meaningful insights.

We thank the reviewers for their insights on efficiency and the relation of the proposed method to contrastive learning. We aim for the responses to be clear in addressing the concerns and questions. If any concerns remain or if further improvements are deemed necessary, please let us know how we can further enhance the work.

1. Complexity Analysis.

We've included the time and space complexity analysis in the general response. The additional costs introduced by our proposed loss are minimal.

2. Concerns Regarding only using first/final layer.

Studying the case where consistency loss is applied only between the first and final layers could be beneficial, as it may further reduce the training time. We conduct additional experiments applying our consistency loss to the first and final layers of various backbone models, with the results presented in Table R3. The second to last column in Table R3 highlights the improvement of applying consistency loss to all layers, compared to the baseline models. The last column shows the improvement when consistency loss is applied only to the first and last layers. As shown, applying consistency loss only to the first and last layers achieves similar performance to applying it to all layers. This suggests our method can be further accelerated with little to no performance sacrifice.

Table R3. Classification performance on TU and OGB datasets for models with consistency loss applied to the first and last layers. The values represent average accuracy for TU datasets and ROC-AUC for the ogbg-molhiv dataset, along with their standard deviations. $\mathcal{L}\_{FL}$ and $\mathcal{L}\_{ALL}$ denote the consistency loss applied to the first and last layers, and to all layers, respectively.

3. Similarity/Difference with Contrastive learning.

This is an interesting question. While both methods assess similarity, our approach emphasizes the consistency across layers rather than merely capturing similarities, as contrastive learning does. To validate this, we applied the GraphCL[1] contrastive learning technique to the GCN model (denoted as GCN+CL) and evaluated its performance and similarity consistency across various datasets. The results, shown in Tables R4 and R5, use accuracy for classification performance and Spearman rank correlation (Section 5.3) for assessing similarity consistency across layers. The last columns present the average decrease in accuracy and rank correlation for GCN+CL compared to GCN+$\mathcal{L}_{\text{consistency}}$.

Table R4. Graph classification accuracy of GCN with contrastive learning applied across various datasets.

Table R5. Spearman rank correlation for graph representations from consecutive layers.

Our method consistently outperforms GCN+CL in both graph classification and improving similarity consistency, highlighting the key differences between the two approaches.

[1]Y. You et al., Graph Contrastive Learning with Augmentations, NeurIPS, 2020

4. Multi-classification.

To demonstrate the effectiveness of our method across diverse datasets, we applied it to REDDIT-MULTI-5K, a 5-class classification dataset. The results, presented in Table R6, show that our method consistently achieves improvements in this task.

Table R6. Graph classification performance on REDDIT-MULTI-5K, measured in accuracy.

We apologize for a mistake in our rebuttal: The second-to-last column in Table R3 should be titled Improvements of $\mathcal{L}_{FL}$ over base models, showing the improvement from applying the loss to the first and last layers. The last column should be titled Improvements of $\mathcal{L}_{ALL}$ over base models, indicating the impact of applying the loss to all layers.

Thank you for taking the time to address my concerns. Just adding a multi-classification dataset does not allay my concerns. In addition, I think that the method of constraining the similarity relationship of the graph layer by layer is not novel enough. I will maintain my review score.

Thank you for your insightful comment. Indeed, in our initial version, we demonstrated that the monotonic decrease principle alone is sufficient to prove the increased decision margin on the training data. We have now explored the effects of combining both principles and found out that they can provide guarantees on the test data.

As a result, we updated our Theorem 3.4 and provided the new proof in the latest version available on arXiv. We will incorporate these updates in the final camera-ready version. Due to the publication delay on arXiv,we have attached a link to the revised document for your reference.

Best regards,

Authors