- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper studies whether GNNs trained on smaller graphs can be used on the original graph without retraining. It uses geometric renormalization to create smaller graphs while preserving important graph properties. The authors evaluate the method using three GNN models on synthetic and real-world datasets. They also compare GR with other graph coarsening methods and analyze the similarity of learned representations across different graph sizes. The results show that training on smaller graphs can reduce training time while maintaining good accuracy in many cases.
Critical strengths
- The paper shows that GNNs can be trained on smaller graphs and used on the original graph without retraining, while keeping good accuracy in many cases. This can help reduce training time.
- The paper evaluates the method on several datasets and GNN models. It also compares against existing graph coarsening methods, which helps demonstrate its effectiveness.
Critical weaknesses
- The experiments mainly focus on homophilic graphs, with no systematic evaluation on heterophilic benchmarks.
- Although training on smaller graphs reduces training time, hyperbolic embedding introduces significant additional cost. The authors provide some computational analysis, but the overall benefit is unclear when considering both the accuracy drop and total computation time.
- It is unclear whether the improved transfer performance comes from preserving graph self-similarity or simply from grouping nodes with similar features and labels. The experiments do not clearly separate these effects.
Questions for authors
- Could the authors include experiments on heterophilic datasets?
- Could the authors compare their method with a randomly initialized GNN, where the message-passing layers are frozen and only the classifier is trained?
- Could the authors explain why some datasets have larger accuracy drops than others and which graph properties affect transfer performance?
- Could the authors show how accuracy and total computation time change as the graph is compressed further, including the cost of hyperbolic embedding?
5 comments
It is unclear whether the improved transfer performance comes from preserving graph self-similarity or simply from grouping nodes with similar features and labels. The experiments do not clearly separate these effects.
We thank the reviewer for this important comment. We agree that distinguishing the contribution of structural self-similarity from the potential benefits of grouping nodes with similar features and labels is essential for understanding the mechanism underlying cross-scale GNN transfer.
First, we emphasize that geometric renormalization (GR) does not explicitly optimize feature or label similarity. Instead, supernodes are constructed by merging consecutive nodes in the latent similarity space, whose coordinates are inferred exclusively from the original network topology. Node features and labels are aggregated only after the geometric partition has been determined. Nevertheless, because latent geometry may correlate with feature similarity and label homophily, this observation alone does not rule out the alternative explanation raised by the reviewer.
Importantly, our experiments already include a control that directly addresses this concern: the Random-T baseline, presented in Appendix A.11.3 (Figures 21 and 22). In this baseline, the original latent coordinates are preserved while the network topology is randomized before renormalization. Because the geometric coordinates and the corresponding supernode assignments remain unchanged, GR and Random-T aggregate exactly the same groups of nodes, resulting in identical supernode features and training labels. The only difference lies in the connectivity structure of the resulting coarse-grained networks.
This comparison therefore isolates the contribution of network structure while controlling for the potential benefits of grouping nodes with similar features and labels. The differences in zero-shot transfer accuracy between GR and Random-T cannot be attributed to feature or label aggregation alone, since these are identical in both conditions. The generally superior transfer performance of GR thus provides evidence that preserving the network's structural organization contributes to successful cross-scale transfer beyond the effects of feature–label aggregation.
The Random-G baseline provides complementary evidence. In this case, the original network topology is preserved while the latent coordinates used to construct the supernodes are randomized. This disrupts the correspondence between the geometric partition and the network's connectivity structure. The resulting differences in transfer performance indicate that retaining the original network topology is not sufficient when the coarse-graining no longer respects the underlying geometric organization. Although Random-G also changes the supernode composition and therefore the aggregated features and labels, its comparison with GR further highlights the importance of the relationship between geometry and topology.
Taken together, these two controls, and especially Random-T, support the interpretation that successful transfer is not simply a consequence of grouping nodes with similar features and labels, but also depends on preserving the compatibility between the coarse-graining partition and the network's structural organization. This is consistent with our hypothesis that self-similar multiscale organization provides a structural basis for cross-scale GNN transfer.
We will revise the manuscript to clarify the role of these complementary controls and make the distinction between structural preservation and feature–label aggregation more explicit.
Could the authors include experiments on heterophilic datasets?
We addressed this comment in our response below.
Could the authors compare their method with a randomly initialized GNN, where the message-passing layers are frozen and only the classifier is trained?
We thank the reviewer for this suggestion. Comparing against a randomly initialized GNN with frozen message-passing layers and a trainable classifier would be an interesting additional experiment. However, our primary focus in this work is on understanding the transferability of learned GNN weights across different graph scales. In particular, our representational similarity experiments show that GNNs trained at different scales learn similar representations, providing insight into why weight transfer is effective. A randomly initialized GNN with frozen message-passing layers would instead evaluate the effectiveness of random feature representations, addressing a related but distinct question.
While this experiment is not included in our current evaluation, we have conducted additional analyses to investigate how learned GNN weights and representations are preserved across scales. Specifically, we compute linear CKA between the first-layer weights of GNNs trained on the original graph and its 32-fold compressed counterpart. Across all four evaluated datasets, geometric renormalization (GR) achieves the highest mean weight similarity, with generally lower values under Random-T, Random-G, and fully randomized renormalization. These findings provide complementary evidence that GR promotes consistency in learned weights and representations across scales.
Table 1. First-layer linear CKA between - and -trained models. The coarse-grain network is 32 times smaller compared to . Values are mean and standard deviation across 10 repeats.
| Dataset | Original GR | Random-T | Random-G | Random |
|---|---|---|---|---|
| Photo | 0.298 ± 0.117 | 0.197 ± 0.094 | 0.217 ± 0.112 | 0.206 ± 0.090 |
| Physics | 0.447 ± 0.110 | 0.232 ± 0.067 | 0.122 ± 0.059 | 0.076 ± 0.042 |
| PubMed | 0.384 ± 0.109 | 0.290 ± 0.103 | 0.077 ± 0.074 | 0.071 ± 0.083 |
| Cora | 0.435 ± 0.088 | 0.382 ± 0.091 | 0.244 ± 0.055 | 0.272 ± 0.077 |
Could the authors explain why some datasets have larger accuracy drops than others and which graph properties affect transfer performance?
We acknowledge that zero-shot GNN transfer is more challenging for some datasets than for others. One possible explanation lies in the complex relationships between network topology, node features, and node labels in real-world networks. Jankowski et al. showed that, for certain networks, topology-only embeddings yield lower node classification accuracy than feature-only embeddings [1]. We hypothesize that such differences in the relative importance of topology and node features may also contribute to the larger drops in transfer accuracy observed for some datasets. Synthetic networks provide a promising framework for systematically investigating these effects. In particular, the HypBench framework allows us to generate networks with varying degrees of topology-feature correlation while independently tuning structural properties. This would enable a more controlled analysis of which network characteristics influence transfer performance and under what conditions zero-shot transfer becomes less effective.
Another possible explanation concerns the choice of hyperparameters. In this work, we use fixed hyperparameters across all experiments to ensure consistency. However, it remains unclear whether optimizing hyperparameters for each dataset would also improve transfer test accuracy. We consider both the interplay between network topology and node features and the role of hyperparameter optimization to be important directions for future research.
[1] Jankowski, R., Hozhabrierdi, P., Boguñá, M., & Serrano, M. Á. (2024). Feature-aware ultra-low dimensional reduction of real networks. npj Complexity, 1(1), 13.
We thank the reviewer for this comment. We acknowledge that our experimental evaluation primarily focuses on homophilic graphs, and we have already identified the extension to heterophilic networks as a direction for future work in the Conclusion section. A systematic investigation of heterophilic benchmarks is beyond the scope of the present study.
We hypothesize that extending our approach to heterophilic networks may require developing a feature-aware renormalization protocol. In the current framework, node features are aggregated by taking the mean feature vector of the merged nodes. While this provides a simple aggregation strategy, it may not adequately capture the feature structure of heterophilic graphs, where neighboring nodes often exhibit dissimilar features. Consequently, directly applying the current aggregation scheme to such networks may lead to a loss of relevant feature information.
Addressing this limitation would require a more careful treatment of node features during renormalization, which we intend to investigate in future work.
In the revised manuscript, we have updated Table 9 to include the accuracy drop alongside the total computational cost. As shown below, the accuracy decreases by only 0.05 on both datasets, while the total runtime, including embedding and renormalization, is reduced by approximately 50% for Physics and 6% for PubMed.
The computational benefits become more pronounced with larger hyperparameter searches, as the embedding cost is incurred only once. We also note that GCN is relatively fast to train. For example, on synthetic networks with approximately 130,000 nodes, GCN training takes around 15 seconds, compared with 70 seconds for GraphSAGE, while embedding takes approximately 400 seconds (Figure 11b). Thus, for more computationally demanding architectures, even a modest hyperparameter search can yield substantial computational savings.
If accepted, we plan to extend this analysis with a more systematic evaluation of the trade-off between transfer accuracy and total computational cost.
Table 1. End-to-end runtime (seconds) for GCN on Physics and PubMed, evaluated over a grid of 4 depths × 4 hidden dimensions with 50 realizations each (800 training runs per dataset). Total time at l=5 includes embedding, renormalization, and training. The accuracy drop is measured relative to the original graph (l=0). Times are reported for A100 GPU.