- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper proposes Adaptive Skeleton Coarsening for text-attributed graphs. It selects semantic anchors using spherical K-means, learns sparse node-to-anchor assignments, and constructs a smaller graph for downstream GNN training. Experiments on 11 benchmarks show competitive accuracy under aggressive compression, along with reduced downstream training time and memory.
Critical strengths
The paper covers a reasonable range of datasets and compression ratios. The comparison with a training-free spherical K-means baseline is useful, and the results at very low compression ratios are encouraging.
Critical weaknesses
- The method mainly combines semantic clustering, learned soft assignments, feature reconstruction, and edge pruning. Most components are familiar from existing graph coarsening methods. While the empirical improvements are useful, I am not convinced that the paper introduces a sufficiently distinct technical idea. More fundamentally, I also question the significance of the research problem itself. Despite combining numerous engineering tricks and design choices, the method achieves relatively modest improvements over strong baselines on several datasets. This raises the question of whether the current problem setting is already approaching saturation, and whether further research in this direction can deliver meaningful practical value.
- The efficiency claims are misleading without accounting for compression cost. For example, on OGBN-Arxiv, the compression cost would therefore require roughly 20 downstream training runs to amortize. 3.The graph-level property objective is not sufficiently validated. Section 3.4 trains a prediction head to recover properties of the original graph, rather than directly matching the properties of the compressed graph. Direct measurements of structural preservation on the final compressed graph are needed to support the proposed mechanism.
- The downstream classifier is trained using original-node labels through the assignment matrix, while validation and testing are performed on the full original graph. Therefore, the reported savings apply primarily to the training stage, rather than to the complete learning and inference pipeline.
- Scalability remains quesstionable. Even on graphs like products, subset is needed. I doubt whether this is really useful for real world industrial scenarios.
Questions for authors
Please answer Qs in weakness.
6 comments
Response to Reviewer 67W7 (2/3)
Q3. Validation of the graph-level property objective
In the overall compression objective, graph-level property prediction is assigned a much smaller weight than semantic reconstruction. Therefore, semantic reconstruction provides the primary compression signal, while graph-level property prediction serves as an auxiliary structural constraint. Despite its small weight, this auxiliary constraint still contributes to improved downstream performance. Removing it lowers mean classification accuracy on all 11 datasets (Appendix D.2, Table 19(a)).
We compute the gap between the means of the predicted and original graph-level property profiles. Let denote the -th component () of the fixed seven-dimensional original-graph property profile defined in Appendix A.3, and its prediction at epoch . For each run, the mean-property gap is
The table reports three-seed mean gaps during the first 200 compression epochs on six datasets at .
| Dataset | Epoch 1 | Epoch 50 | Epoch 100 | Epoch 150 | Epoch 200 |
|---|---|---|---|---|---|
| OGBN-Arxiv | 1.574 | 1.485e-2 | 1.08e-2 | 9.338e-3 | 8.715e-3 |
| TAPE | 1.588 | 1.286e-2 | 1.012e-2 | 8.491e-3 | 8.263e-3 |
| Cora | 1.211 | 5.64e-3 | 4.787e-3 | 3.741e-3 | 3.181e-3 |
| Actor | 1.002 | 4.058e-2 | 3.787e-3 | 3.244e-3 | 3.02e-3 |
| CiteSeer | 1.368 | 8.115e-3 | 6.774e-3 | 5.817e-3 | 5.203e-3 |
| WikiCS | 1.096 | 7.429e-3 | 4.96e-3 | 4.048e-3 | 4.042e-3 |
As training progresses, the gap becomes substantially smaller across all six datasets, indicating that the predicted property mean becomes increasingly close to the original graph’s property mean. This suggests that the compressed graph increasingly preserves the structural properties of the original graph. Appendix D.3, Figure 4 visualizes the gap between the predicted and original property-mean curves averaged over three seeds.
Response to Reviewer 67W7 (3/3)
Q4. Scope of the downstream efficiency savings
We thank the reviewer for highlighting the scope of the reported efficiency gains.
Training-stage measurements. Table 4 reports downstream GCN training efficiency. GNN message passing operates on the skeleton graph, and supervision uses original-node labels. The measured training step includes lifting skeleton logits through the assignment matrix and computing the loss on original training nodes. Including this supervision overhead, ASC achieves 1.81–3.26× training speedups and uses 3.5%–16.5% of full-graph training peak GPU memory.
Implications for the downstream workflow. Under the original protocol, validation and testing use the original graph. Overall downstream speedup therefore depends on the time spent in skeleton-based training and original-graph evaluation, including validation frequency. Peak GPU memory during downstream training and evaluation depends on both stages. The measurement scope of Table 4 is specified in its caption and the appendix efficiency description.
Extending the savings to inference. We additionally evaluate skeleton-based validation and testing, using the sparse assignment matrix to recover original-node predictions. Results for OGBN-Arxiv, Photo, and Computer are shown below.
| Dataset | OGBN-Arxiv | Photo | Computer |
|---|---|---|---|
| Original accuracy (%) | 74.01 ± 0.32 | 79.02 ± 0.64 | 85.64 ± 0.28 |
| Skeleton accuracy (%) | 69.88 ± 0.34 | 65.93 ± 3.20 | 64.29 ± 1.35 |
| Original inference (ms) | 20.685 ± 0.142 | 12.023 ± 0.053 | 17.242 ± 0.063 |
| Skeleton inference (ms) | 2.288 ± 0.058 | 1.194 ± 0.028 | 1.550 ± 0.020 |
| Speedup | 9.05 ± 0.22× | 10.08 ± 0.19× | 11.13 ± 0.19× |
| Original peak memory (MiB) | 5983.8 ± 0.0 | 3870.2 ± 0.0 | 5699.7 ± 0.0 |
| Skeleton peak memory (MiB) | 355.1 ± 0.7 | 122.2 ± 0.4 | 213.3 ± 0.3 |
Entries report mean ± sample standard deviation over three runs. Speedup is calculated for each matched seed and then averaged. Inference timing includes the GCN forward pass, assignment-based lifting for skeleton prediction, and prediction generation. Peak allocated GPU memory includes the resident model and prediction inputs.
Across all 11 datasets, skeleton-based prediction accelerates inference on nine datasets and reduces inference peak GPU memory by 71.1%–98.6%. Compared with original-graph evaluation, mean accuracy decreases by 4.13, 13.09, and 21.35 percentage points on OGBN-Arxiv, Photo, and Computer, respectively. These results demonstrate that ASC can extend resource savings to inference when skeleton-based prediction is adopted, with a dataset-dependent accuracy trade-off.
The experimental settings and complete ASC accuracy and inference-efficiency results across all 11 datasets are provided in Appendix E, Table 21.
Q5. Large-graph scalability and industrial applicability
We thank the reviewer for raising the question of scalability and practical applicability.
Computational cost and memory control. ASC’s exhaustive node-to-anchor similarity computation has complexity . Chunking limits temporary similarity storage to , where is the node chunk size. Sampled reconstruction, streamed feature aggregation, and chunked edge contraction further limit intermediate memory usage.
Million-node evaluation. To assess scalability beyond the Products subset, we additionally evaluate ASC on the full OGBN-Products graph with 2,449,029 nodes, using 80 compressor epochs on an NVIDIA RTX PRO 6000 GPU.
| Configuration | Original graph | ASC, | ASC, |
|---|---|---|---|
| Test accuracy (%) | 87.49 | 84.59 | 82.01 |
| Compression time (min) | — | 127.96 | 16.98 |
| Compressor training peak GPU memory (GiB) | — | 59.57 | 57.89 |
| Mean GCN training time per epoch (ms) | 390.68 | 72.35 | 34.39 |
These results demonstrate ASC’s feasibility on the complete 2.45-million-node graph under the evaluated GPU budget and quantify its accuracy and resource costs. Each resulting skeleton can be reused across downstream training runs, allowing its upfront construction cost to be amortized when reused sufficiently often. Practical applicability depends on available GPU memory, upfront compression time, and acceptable accuracy loss. Full experimental settings and results are provided in Appendix C.5, Table 15.
Response to Reviewer 67W7 (1/3)
Thank you for reviewing our work. Changes in the revised manuscript are highlighted in blue.
Q1. Technical novelty and practical significance
We appreciate the reviewer’s concerns regarding technical distinctiveness and practical significance.
Technical contribution. ASC learns node grouping according to the semantic information recoverable from the compressed representatives. This addresses a limitation of fixed semantic grouping, whose assignments follow the original embedding geometry without adapting to the features constructed after aggregation. ASC couples a joint semantic–structural encoder with anchor-centered feature fusion. Sparse multi-anchor assignments let each node contribute to several compatible representatives across graph neighborhoods, and gated fusion enriches each anchor with assigned-node context while retaining its own representation. The same map aggregates information into representative features and recovers original-node embeddings from them. Reconstruction errors therefore train both node-to-anchor compatibility and representative features, making grouping and information retention adapt together. Full top-k assignments support semantic aggregation, and truncated assignments control edge expansion during contraction. Under identical frozen Qwen3 embeddings and downstream GCN protocols, ASC achieves higher mean accuracy than SKM-Soft and k-Center-Greedy on all 11 datasets at r=0.1, demonstrating the benefit of this learned compression design.
Performance gains and problem significance. Improvements over strong baselines are modest on some datasets at r=0.1. Under the more stringent budget of r=0.01, ASC achieves higher mean accuracy than UGC, AH-UGC, and Graph-Skeleton across all 11 datasets (Appendix C.1, Table 9). Gains over Graph-Skeleton include 30.07 percentage points on OGBN-Arxiv and 33.05 points on WikiCS. These results show that substantial accuracy differences remain between compression methods under stringent budgets. Improving predictive performance at these budgets is practically valuable when smaller training graphs are needed to reduce GPU memory use or support repeated downstream training.
Practical value. ASC exports a fixed skeleton that supports different downstream architectures and training runs without retraining the compressor. On the five datasets in Table 4, it reduces downstream GCN training peak memory to 3.5%–16.5% of full-graph training and provides 1.81–3.26× training speedups at r=0.1. Reusing the skeleton can amortize its construction cost across repeated downstream training runs. The compression cost and training-time break-even estimates are detailed in Q2.
Q2. Compression cost and amortization
We thank the reviewer for highlighting the importance of accounting for compression cost.
ASC separates one-time skeleton construction from repeated downstream training. The fixed skeleton and assignment map can be reused across random initializations and downstream hyperparameter settings. Our multi-backbone experiments further demonstrate reuse across architectures without retraining the compressor, allowing multiple downstream training runs to share the same construction cost.
Across the five datasets in Table 4, skeleton-based GCN training achieves 1.81–3.26× speedups and uses 3.5%–16.5% of full-graph training peak GPU memory. These training-stage memory savings apply from the first run, while training-time savings accumulate as the skeleton is reused.
To account for construction cost, let C denote compression time and To,Ts denote accumulated training-step times over a fixed 300-epoch budget on the original and skeleton graphs, respectively. The estimated break-even number of runs is
mBE=⌈To−TsC⌉.
Across the five datasets, the estimated break-even point ranges from 8 to 24 training runs. On OGBN-Arxiv, the estimated training-step times are 6.09 seconds on the skeleton and 17.55 seconds on the original graph per run, yielding an estimated break-even point of 19 runs. Compression times are reported in Figure 3, and per-dataset amortization estimates are provided in Appendix C.4, Table 14.