acceptodds
Under review as a conference paper at ICLR 2027

Adaptive Skeleton Coarsening for Text-Attributed Graphs

Abstract

Text-attributed graphs combine relational structure with rich node text, but their large scale and high-dimensional text semantics make downstream graph learning costly. Existing graph compression methods are primarily designed around topology or generic node attributes and typically do not treat pretrained text semantics as a primary signal for compression decisions, limiting their ability to exploit the rich semantics encoded in node text. We present Adaptive Skeleton Coarsening (ASC), a semantic-first framework that uses pretrained text embeddings as the primary compression signal and structural descriptors as complementary signals. A joint encoder maps these signals into a shared assignment space, where ASC adaptively learns sparse soft node-to-anchor assignments primarily through semantic reconstruction, together with an auxiliary graph-level property prediction objective. In downstream evaluation, the compressed graph replaces the original graph during model training. At a compression ratio of r=0.1, ASC achieves the highest mean classification accuracy on all 11 benchmarks, while substantially reducing the peak memory consumption and training time of downstream GCNs on the evaluated graphs. Under extreme compression at r=0.01, ASC still maintains robust and superior classification performance.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
Graph Coarsening, Semantic-Aware Graph Learning, Text-Attributed Graphs, Graph Neural Networks

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_67W7OpenReview ↗
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
  1. 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.
  2. 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.
  3. 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.
  4. 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
AuthorsOpenReview ↗

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-kk 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.1r=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.1r=0.1. Under the more stringent budget of r=0.01r=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.1r=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 CC denote compression time and To,TsT_o,T_s 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=⌈CTo−Ts⌉.m_{\mathrm{BE}}=\left\lceil\frac{C}{T_o-T_s}\right\rceil.

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.

AuthorsOpenReview ↗

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 ϕj\phi_j denote the jj-th component (j=1,…,7j=1,\ldots,7) of the fixed seven-dimensional original-graph property profile defined in Appendix A.3, and ϕ^j(t)\hat{\phi}_j(t) its prediction at epoch tt. For each run, the mean-property gap is

Δ(t)=17∣∑j=17(ϕ^j(t)−ϕj)∣.\Delta(t)=\frac{1}{7}\left|\sum_{j=1}^{7}\left(\hat{\phi}_j(t)-\phi_j\right)\right|.

The table reports three-seed mean gaps during the first 200 compression epochs on six datasets at r=0.1r=0.1.

DatasetEpoch 1Epoch 50Epoch 100Epoch 150Epoch 200
OGBN-Arxiv1.5741.485e-21.08e-29.338e-38.715e-3
TAPE1.5881.286e-21.012e-28.491e-38.263e-3
Cora1.2115.64e-34.787e-33.741e-33.181e-3
Actor1.0024.058e-23.787e-33.244e-33.02e-3
CiteSeer1.3688.115e-36.774e-35.817e-35.203e-3
WikiCS1.0967.429e-34.96e-34.048e-34.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.

AuthorsOpenReview ↗

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.

DatasetOGBN-ArxivPhotoComputer
Original accuracy (%)74.01 ± 0.3279.02 ± 0.6485.64 ± 0.28
Skeleton accuracy (%)69.88 ± 0.3465.93 ± 3.2064.29 ± 1.35
Original inference (ms)20.685 ± 0.14212.023 ± 0.05317.242 ± 0.063
Skeleton inference (ms)2.288 ± 0.0581.194 ± 0.0281.550 ± 0.020
Speedup9.05 ± 0.22×10.08 ± 0.19×11.13 ± 0.19×
Original peak memory (MiB)5983.8 ± 0.03870.2 ± 0.05699.7 ± 0.0
Skeleton peak memory (MiB)355.1 ± 0.7122.2 ± 0.4213.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 O(NKdh)O(NKd_h). Chunking limits temporary similarity storage to O(BK)O(BK), where BB 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.

ConfigurationOriginal graphASC, r=0.1r=0.1ASC, r=0.01r=0.01
Test accuracy (%)87.4984.5982.01
Compression time (min)—127.9616.98
Compressor training peak GPU memory (GiB)—59.5757.89
Mean GCN training time per epoch (ms)390.6872.3534.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.

Reviewer_exdkOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper presents Adaptive Skeleton Coarsening (ASC), a label-free compression method for text-attributed graphs. ASC first selects semantic anchors by applying spherical KK-means to frozen pretrained text embeddings. It then combines semantic and structural features to learn a sparse soft-assignment matrix MM from original nodes to anchors. Skeleton-node features are constructed through gated semantic aggregation, while the graph structure is contracted as M⊤AMM^\top A M and sparsified by edge pruning. The compressor is trained using semantic reconstruction and graph-level property prediction objectives. A downstream GNN is trained on the resulting skeleton graph, with skeleton predictions mapped back to the original nodes through MM. Across 11 node-classification benchmarks, ASC reports strong accuracy under both moderate and extreme compression, while reducing downstream GNN training memory and runtime.

Critical strengths

The semantic-first design is well motivated for text-attributed graphs. Most existing coarsening methods prioritize topology, even though node text is often highly predictive of downstream labels.

The compressed graph is reusable across downstream architectures. ASC exports an explicit weighted skeleton rather than generating model-specific synthetic data. This makes the method compatible with GCN, GAT, GraphSAGE, and even MLP-based pipelines, which improves its practical value.

The empirical evaluation is broad and practically relevant. ASC is tested on 11 datasets, multiple compression ratios, and several downstream backbones. The method preserves strong classification performance even at r=0.01r=0.01, while substantially reducing downstream training memory.

Critical weaknesses

The contribution of graph coarsening is not fully separated from that of pretrained text embeddings. Removing semantic features causes a very large performance drop, whereas the structural descriptors and graph-property objective provide relatively modest gains on several datasets. A stronger text-only clustering or semantic coreset baseline would help determine how much improvement comes from the learned graph construction itself.

The node-to-anchor assignment may become expensive on very large graphs. The reported search cost contains an O(NKdh)O(NKd_h) term.

The evaluation mainly demonstrates training-time compression. The downstream GNN is trained on the skeleton graph, but its parameters are applied to the original graph for validation and testing. Therefore, the original graph is still required at inference time, and the reported results do not fully establish the effectiveness of the skeleton as a standalone compressed graph.

Questions for authors

Can the authors compare ASC with a stronger text-only clustering or semantic coreset baseline using the same pretrained embeddings and downstream evaluation protocol?

How does the O(NKdh)O(NKd_h) node-to-anchor assignment scale to substantially larger graphs? Could approximate nearest-neighbor search reduce this cost without affecting compression quality?

Can the authors report accuracy and inference efficiency when prediction is performed directly on the skeleton graph, without returning to the original graph at validation and test time?

4 comments
AuthorsOpenReview ↗

Response to Reviewer exdk (1/2)

We appreciate your careful reading of our manuscript and your constructive feedback. In the following, we respond to the concerns and questions you have raised.

Q1. Stronger text-only baselines

We evaluate two complementary semantic baselines using the same frozen Qwen3 embeddings, compression ratio, and downstream GCN protocol: SKM-Soft tests fixed semantic clustering, while k-Center-Greedy tests coverage-based semantic representative selection.

SKM-Soft runs spherical KK-means and selects the original node nearest each cluster centroid as its representative. k-Center-Greedy selects representatives through farthest-first traversal in the normalized embedding space. Both then apply the same fixed-space top-3 sparse soft assignment, feature aggregation, edge contraction, and pruning procedures. These comparisons assess whether fixed semantic clustering or coverage-based representative selection can achieve comparable compression quality without learning the assignment space.

Representative results at r=0.1r=0.1 are shown below. Entries report test accuracy (%) as mean ± sample standard deviation over three runs.

DatasetASCSKM-Softk-Center-Greedy
PubMed88.36 ± 0.5184.13 ± 0.2284.60 ± 1.00
WikiCS82.22 ± 0.9978.27 ± 0.3073.54 ± 0.05
Cora87.88 ± 2.0384.25 ± 1.2378.78 ± 1.39

ASC achieves higher mean accuracy than both semantic baselines across all 11 datasets, demonstrating the empirical benefit of its learned compression design beyond fixed semantic clustering and coverage-based representative selection. Complete results are reported in Table 1 and Appendix C.1, Table 8.

Q2. Assignment scalability and approximate nearest-neighbor search

We thank the reviewer for raising this scalability concern. We assess the practical scalability of exhaustive assignment through full OGBN-Products compression and GPU-based approximate nearest-neighbor (ANN) assignment experiments.

Million-node scalability. ASC’s exhaustive node-to-anchor similarity computation costs O(NKdh)O(NKd_h) per full assignment pass. At a fixed compression ratio, K≈rNK\approx rN, giving O(rN2dh)O(rN^2d_h) scaling for this computation. Chunking limits temporary similarity storage to O(BK)O(BK), where BB is the node chunk size. Sparse assignments and sampled reconstruction further control intermediate memory usage (Sections 3.2–3.5).

We additionally evaluated the full OGBN-Products graph (2,449,029 nodes) with the existing ASC implementation on an NVIDIA RTX PRO 6000 GPU, training the compressor for 80 epochs at each ratio.

ConfigurationOriginal graphASC, r=0.1r=0.1ASC, r=0.01r=0.01
Test accuracy (%)87.4984.5982.01
Compression time (min)—127.9616.98
Compressor training peak GPU memory (GiB)—59.5757.89
Mean GCN training time per epoch (ms)390.6872.3534.39

These single-run results demonstrate ASC's feasibility on the complete 2.45-million-node graph, with a 2.90-percentage-point accuracy loss at r=0.1r=0.1 relative to full-graph training. The shorter compression time at r=0.01r=0.01 is consistent with the smaller anchor budget. Both skeletons reduce downstream GCN training time per epoch. Validation and testing use the original graph.

ANN assignment. To investigate whether approximate search could reduce assignment cost, we implemented GPU Faiss IVF-Flat retrieval, followed by exact similarity recomputation over retrieved candidates and the same sparse assignment weighting.

DatasetExact accuracy (%)ANN accuracy (%)Exact compression (s)ANN compression (s)
PubMed88.36 ± 0.5186.37 ± 1.7026.24 ± 0.14158.06 ± 2.61
OGBN-Arxiv74.01 ± 0.3273.91 ± 0.38210.53 ± 1.71468.86 ± 1.78
WikiCS82.22 ± 0.9981.59 ± 0.2144.65 ± 0.59183.37 ± 5.60

Values are means ± sample standard deviations over three runs. Exact-search entries are the paper-reported results, while ANN entries are newly measured.

In the evaluated ANN implementation, we repeatedly rebuilt the index as the joint encoder updated the anchor representations during training. We recorded 641, 401, and 641 index constructions on PubMed, OGBN-Arxiv, and WikiCS, respectively, with mean cumulative index-building times of 79.81, 70.42, and 79.35 seconds per run.

The evaluated ANN implementation yields lower mean accuracy and longer compression times on all three datasets. We therefore retain chunked exact search in the current implementation.

AuthorsOpenReview ↗

Response to Reviewer exdk (2/2)

Q3. Skeleton-based validation, testing, and inference efficiency

Our original evaluation trains the GNN on the compressed graph and applies the learned parameters to the original graph for validation and testing. Related graph-coarsening protocols, such as FGC, also train GNNs on coarsened graphs to predict original-node labels. Following the reviewer's suggestion, we additionally perform validation and testing entirely through the skeleton graph. This prediction path does not access the original graph's features or edges.

Skeleton-based prediction. We evaluate ASC, AH-UGC, and FGC under this setting at r=0.1r=0.1. Representative test accuracies (%) are reported as mean ± sample standard deviation over three runs.

DatasetASCAH-UGCFGC
PubMed84.56 ± 0.6648.68 ± 0.4239.93 ± 0.00
WikiCS72.33 ± 1.9625.62 ± 0.0523.29 ± 0.24
Cora75.52 ± 2.6932.29 ± 0.5530.14 ± 0.11

ASC achieves higher mean accuracy than AH-UGC on all 11 datasets. It also exceeds FGC on all five datasets where FGC produces valid results. Using ASC's paper-reported original-graph evaluation results as references, skeleton-based prediction yields mean accuracies lower by 3.80, 9.89, and 12.36 percentage points on PubMed, WikiCS, and Cora, respectively. These results demonstrate that ASC supports original-node prediction using only the compressed graph and its assignment map, with an accuracy trade-off relative to full-graph evaluation.

Inference efficiency. We directly measure inference latency and peak GPU memory under both evaluation protocols. In both protocols, GCNs are trained on the skeleton graph for 300 epochs without early stopping, with checkpoints selected using their respective validation paths.

DatasetOGBN-ArxivPhotoComputer
Original accuracy (%)74.01 ± 0.3279.02 ± 0.6485.64 ± 0.28
Skeleton accuracy (%)69.88 ± 0.3465.93 ± 3.2064.29 ± 1.35
Original inference (ms)20.685 ± 0.14212.023 ± 0.05317.242 ± 0.063
Skeleton inference (ms)2.288 ± 0.0581.194 ± 0.0281.550 ± 0.020
Speedup9.05 ± 0.22×10.08 ± 0.19×11.13 ± 0.19×
Original peak memory (MiB)5983.8 ± 0.03870.2 ± 0.05699.7 ± 0.0
Skeleton peak memory (MiB)355.1 ± 0.7122.2 ± 0.4213.3 ± 0.3

Entries summarize three runs using mean ± sample standard deviation. Skeleton-based inference is faster on nine of the 11 datasets. CiteSeer and Cora show small latency increases of approximately 10% and 8%, respectively. Peak GPU memory includes the resident model and prediction inputs. Skeleton-based inference reduces this peak by approximately 71.1%–98.6% across all 11 datasets relative to original-graph inference.

For OGBN-Arxiv, Photo, and Computer, the corresponding mean accuracy decreases are 4.13, 13.09, and 21.35 percentage points. Together, these results quantify the accuracy and resource trade-off of original-node prediction through the skeleton graph.

The experimental settings and complete ASC accuracy and inference-efficiency results across all 11 datasets are provided in Appendix E, Table 21.

Thank you for the detailed response. I will maintain my current score.

AuthorsOpenReview ↗

Response to Reviewer exdk

Thank you very much for your positive evaluation of our work. We hope that our research will make some contribution to the development of the graph coarsening field, which would not have been possible without your efforts.

Reviewer_SjvXOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes Adaptive Skeleton Coarsening (ASC), a graph compression framework for text-attributed graphs. It combines pretrained text embeddings with structural descriptors to learn sparse node-to-anchor assignments, optimizing semantic reconstruction and graph-level property prediction. Experiments on 11 benchmarks demonstrate competitive classification accuracy and reduced downstream GNN training costs.

Critical strengths
  1. The paper addresses the practical problem of efficient GNN training on text-attributed graphs.

  2. The evaluation covers 11 datasets, multiple compression ratios, and different downstream architectures, with generally strong empirical results.

  3. The proposed sparse graph construction achieves considerable reductions in downstream training memory consumption.

Critical weaknesses
  1. The paper argues that existing graph coarsening methods overlook pretrained text semantics. However, feature-aware approaches such as FGC and TACO already incorporate node attributes or learned representations into compression. Since pretrained text embeddings are also node features, the paper does not clearly establish why text-attributed graphs require a fundamentally different coarsening strategy.

  2. The main components, including K-means anchor selection, learned soft assignment, feature reconstruction, and graph contraction, are largely established techniques. Their combination appears incremental, and the paper does not sufficiently distinguish its technical contributions from existing feature-aware coarsening frameworks.

  3. Preserving text embeddings through reconstruction does not necessarily preserve task-relevant graph information. Moreover, predicting original graph properties from compressed representations does not guarantee that the compressed graph actually preserves those properties. The connection between these surrogate objectives and downstream predictive performance remains insufficiently explained.

Questions for authors

Please refer to weakness.

8 comments
AuthorsOpenReview ↗

Response to Reviewer SjvX (1/3)

Thank you for reviewing our work. Changes in the revised manuscript are highlighted in blue.

Q1. Positioning relative to feature-aware coarsening

Under aggressive compression, a node’s text may contain information relevant to several representatives, and semantically related nodes may lie far apart in the graph. FGC promotes disjoint node-to-supernode assignments, which can limit a node’s contribution to multiple semantically compatible representatives. TACO merges clusters along existing edges, so semantically related nodes in disconnected components cannot share a representative. Grouping distant nodes within a component also requires successive merges involving intermediate nodes. ASC addresses these limitations by learning sparse multi-anchor assignments across graph neighborhoods and connected components, with semantic reconstruction jointly guiding the assignments and representative features.

FGC jointly optimizes a loading matrix and coarse-node features through feature reconstruction and graph regularization. ASC uses a joint semantic–structural encoder to learn which nodes contribute to each anchor, and gated feature fusion combines the anchor’s own representation with assignment-weighted context. This gives each representative access to both its original semantic information and information from other compatible nodes. Reconstructing the frozen text embeddings jointly trains the encoder and feature fusion, so both adapt to improve reconstruction of the original semantic information.

TACO uses representation similarity to rank existing edges for merging, making graph connectivity a prerequisite for grouping nodes. ASC directly learns node-to-anchor assignments, allowing semantically compatible nodes to share a representative across neighborhoods and connected components. It then contracts the original edges using truncated assignment weights. This enables semantic grouping beyond local connectivity while incorporating the original graph’s relations into the skeleton.

Experimental comparison. We compare the methods using identical frozen Qwen3 embeddings and downstream GCN protocols. TACO is evaluated through a static-graph adaptation of its coarsening module. At r=0.1r=0.1, ASC achieves higher mean accuracy on all nine datasets where the adapted TACO baseline reaches the target ratio. The table reports test accuracy (%) as mean ± sample standard deviation over three runs for the six datasets where all three methods yield valid results.

DatasetASCFGCTACO
PubMed88.36 ± 0.585.25 ± 0.453.74 ± 4.4
WikiCS82.22 ± 1.057.95 ± 0.429.46 ± 6.7
Product-subset83.85 ± 0.844.47 ± 3.624.49 ± 4.5
Cora87.88 ± 2.080.50 ± 1.144.83 ± 10.1
Photo79.02 ± 0.661.34 ± 0.541.77 ± 0.4
Actor70.19 ± 1.455.46 ± 10.353.17 ± 3.9

ASC achieves higher mean accuracy than both methods on all six datasets. Complete TACO results, including the two datasets where the target ratio was not achieved, are provided in Appendix C.1, Table 8.

AuthorsOpenReview ↗

Response to Reviewer SjvX (2/3)

Q2. Technical novelty

Under aggressive compression, preserving semantic differences between nodes becomes difficult when many nodes must share a small set of representatives. Hard assignment reconstructs nodes within a group from one shared representative, and fixed semantic grouping cannot adjust its assignments to information lost during aggregation. ASC couples reconstruction-guided assignment learning with anchor-centered feature construction and sparse edge contraction through a shared node-to-anchor map. This learns how nodes share representatives and what information those representatives retain, supporting node-specific semantic recovery while controlling topology expansion.

Preserving semantics through learned representative sharing. ASC’s joint semantic–structural encoder learns sparse multi-anchor assignments across graph neighborhoods. Each node recovers its embedding through its own weighted combination of representative features, allowing semantic differences to be expressed within a shared representative set. Anchor-centered feature fusion retains an explicit anchor-specific representation and enriches it with normalized, gated context from assigned nodes. Context normalization controls the scale of the aggregated features, and the learned gate regulates their contribution to each anchor. The same map aggregates information into representative features and reconstructs original-node embeddings from them. Reconstruction errors therefore update both the joint encoder and feature fusion according to the information recoverable after aggregation. This makes node grouping and representative features adapt together during compression.

Controlling the cost of semantic sharing. Multi-anchor assignments increase the potential number of anchor-pair contributions generated during edge contraction. Restricting assignments for both feature aggregation and contraction would also reduce the semantic context available to representatives. ASC separates these operations through different assignment budgets. For KK anchors, let keff=min⁡(k,K)k_{\mathrm{eff}}=\min(k,K). Feature aggregation retains the full top-keffk_{\mathrm{eff}} assignments, and edge contraction uses their top-qq-truncated counterpart, with q=min⁡(2,keff)q=\min(2,k_{\mathrm{eff}}). Contracting through the full assignment permits up to keff2k_{\mathrm{eff}}^2 contributions per original edge, and truncation limits this to at most q2q^2. Subsequent pruning controls the exported graph’s sparsity, making multi-anchor semantic sharing compatible with efficient downstream message passing.

Experimental support. Under matched 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.1r=0.1, supporting the benefit of the complete learned compression design. Reconstruction ablations show its contribution to downstream accuracy, and cosine diagnostics show improved alignment between original and recovered semantic representations on all 11 datasets. The default multi-anchor configuration also achieves higher mean accuracy than hard assignment on all four datasets in Table 17.

AuthorsOpenReview ↗

Response to Reviewer SjvX (3/3)

Q3. Connection between the objectives and downstream performance

Both objectives affect downstream learning through the skeleton features and assignment map produced by the shared compressor. Semantic reconstruction trains these outputs to recover the original text embeddings, and property-prediction gradients provide complementary supervision about the original graph’s structural characteristics. The skeleton features and contracted adjacency are used for GNN message passing, and the assignment map lifts skeleton logits to compute the loss on original training nodes. Classification ablations show that removing either objective lowers mean downstream accuracy.

Semantic reconstruction. On the three datasets below, Full achieves higher cosine similarity than w/o Rec. in each of the three runs. Entries report mean ± sample standard deviation.

DatasetFull cosine ↑w/o Rec. cosine ↑
PubMed0.686 ± 0.0760.422 ± 0.016
WikiCS0.638 ± 0.0480.331 ± 0.010
Cora0.754 ± 0.0060.360 ± 0.024

These results indicate improved angular alignment between the original and reconstructed semantic representations. The metric definition and complete results across all 11 datasets are provided in Appendix D.2, Table 20.

Graph-level property prediction. We examine predictions of the seven graph-level properties during the first 200 compression epochs on six datasets at r=0.1r=0.1. Each curve shows the mean of the seven property components, averaged over three seeds. Across the six datasets, the curves show an overall trend of convergence as training progresses, indicating that the predicted property mean becomes increasingly close to the original graph's property mean. Property definitions are provided in Appendix A.3, and the curves are presented in Appendix D.3, Figure 4.

Downstream performance. Classification ablations directly evaluate the contribution of each objective to downstream predictive performance. The table reports test accuracy (%) as mean ± sample standard deviation over three runs.

DatasetFullw/o Rec.w/o Prop.
PubMed88.36 ± 0.5183.83 ± 1.2387.74 ± 0.38
WikiCS82.22 ± 0.9960.97 ± 11.3580.39 ± 0.80
Cora87.88 ± 2.0380.63 ± 2.0987.33 ± 1.68

Removing reconstruction reduces mean accuracy by 4.53, 21.25, and 7.25 percentage points on PubMed, WikiCS, and Cora, respectively. Removing property prediction yields smaller mean reductions of 0.62, 1.83, and 0.55 points. These results show that semantic reconstruction makes the larger contribution to downstream accuracy, with property prediction providing an additional improvement.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.