- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper proposes a graph coarsening method that preserves the block Krylov subspace generated by node features and their graph propagations. The authors establish theoretical bounds relating the worst-case transfer error of polynomial graph filters to a projection-residual objective, which is approximately minimized through multilevel Ward clustering. An edge pruning strategy is further introduced to control graph density and improve efficiency. Experiments on nine node-classification datasets with five GNN backbones demonstrate consistent accuracy improvements over existing coarsening methods across different reduction ratios. The proposed method also achieves faster coarsening and substantial end-to-end training speedups.
Critical strengths
-
This paper establishes meaningful bounds connecting polynomial-filter transfer errors to a tractable graph coarsening objective.
-
Extensive evaluations across nine datasets and five GNN backbones demonstrate consistent improvements over strong baselines. The proposed method achieves competitive coarsening efficiency and substantial end-to-end training speedups, demonstrating its scalability to large graphs.
Critical weaknesses
The theoretical guarantees do not cover the edge-pruned propagation operator used in practice, limiting their applicability to the final method.
Questions for authors
-
Theorem 1 assumes the coarse propagation operator (S_c = RSR^+), whereas the actual method uses an edge-pruned operator. How significant is the resulting approximation error, and can the authors provide evidence that the theoretical guarantees remain meaningful after edge pruning?
-
Figure 3(b) shows limited improvements beyond (K=1), while Appendix H indicates that the worst-case transfer error is dominated by the zeroth-order term on eight of nine datasets. What evidence supports the practical necessity of preserving higher-order Krylov information?
3 comments
Response to Reviewer XM7d: Question 2
Response to Question 2
Thank you. We do not claim that is needed on every graph: one propagation step is enough in most dataset–ratio settings, but not in all, and which ones cannot be known before coarsening. Figure 3b covered five datasets at 90%, so we extended the sweep to all nine datasets and three ratios (GCN, five training seeds).
When helps. should help when (i) the task uses orders 2–3 and (ii) a one-step coarsening loses them. Table R3.1 reports both, with the accuracy of against .
Table R3.1. Full graph: accuracy of a degree-3 minus a degree-1 polynomial filter on the uncoarsened graph (pp). Err: change in the order-2 / order-3 error from the to the partition (%). Acc: GCN accuracy, minus (pp); bold: over five training seeds.
| Dataset | Full graph (deg. 3 − deg. 1) | Err 80% | Acc 80% | Err 90% | Acc 90% | Err 99% | Acc 99% |
|---|---|---|---|---|---|---|---|
| pokec | +9.8 | −10 / −12 | +4.2 | −11 / −13 | +4.4 | −8 / −10 | +0.1 |
| ogbn-products | +7.2 | −10 / −12 | +0.7 | −12 / −15 | +0.4 | −7 / −9 | +0.7 |
| twitch-gamers | +2.0 | −13 / −12 | +0.6 | −10 / −10 | −0.2 | −4 / −6 | +1.7 |
| snap-patents | +4.3 | −4 / −6 | −0.1 | −4 / −5 | −0.5 | −3 / −4 | +1.4 |
| ogbn-arxiv | +5.0 | −1 / −1 | −0.4 | −2 / −1 | +0.1 | −2 / −2 | +0.8 |
| arxiv-year | +2.4 | −1 / −1 | +0.1 | −2 / −1 | +0.5 | −2 / −2 | +0.6 |
| ogbn-mag | +2.3 | −3 / −3 | −0.1 | −2 / −3 | −0.2 | −1 / −2 | −0.1 |
| reddit2 | +0.9 | −1 / −1 | 0.0 | −1 / −1 | −0.1 | −1 / −1 | −0.3 |
| igb-small | −0.3 | −2 / −2 | 0.0 | −1 / −1 | 0.0 | +1 / +1 | 0.0 |
Condition (i) holds on eight of the nine datasets, so (ii) decides. Where loses the most of orders 2–3 at every ratio (pokec, ogbn-products and twitch-gamers), gives six of the eight significant gains. On snap-patents, where the loss is moderate, the result is mixed. Where the two partitions differ by at most 3% at these orders, gives one small gain; this includes ogbn-arxiv and ogbn-mag, whose tasks do use orders 2–3. A large error reduction thus marks the datasets that gain, but not every ratio: ogbn-products and twitch-gamers at 90% and pokec at 99% show no significant gain.
Accuracy on all nine datasets. Over the 27 dataset–ratio cells, and are indistinguishable in 18; is significantly better in 8 and worse in 1 (bold in Table R3.1). Table R3.2 gives the cost of fixing in advance: the gap to the best for the same dataset and ratio.
Table R3.2. Gap to the best in each dataset–ratio cell (pp), mean / worst.
| All 27 cells | 1.33 / 6.15 | 0.79 / 5.45 | 0.57 / 5.21 | 0.26 / 1.25 | 0.18 / 0.69 | 0.30 / 1.00 |
| Without pokec | 0.91 / 3.63 | 0.42 / 1.97 | 0.17 / 0.94 | 0.19 / 0.57 | 0.20 / 0.69 | 0.31 / 1.00 |
Every falls more than 5 pp below the best on pokec, while every stays within 1.25 pp of it in all cells; without pokec, still falls up to 2.0 pp below it, against 0.6 pp for . adds at most 10 s of coarsening time over and matches the three layers or hops of GCN, GraphSAGE, SGC and SIGN.
What Appendix H shows, and what it cannot. Using the partition created with , Appendix H reports , the largest of the per-order errors (Proposition 1). What changes is the error at orders 2–3, below this maximum (Table R3.1): on ogbn-products at 90%, lowers the order-3 error from 0.119 to 0.101 while rises from 0.430 to 0.460. A maximum over orders cannot show this; the per-order errors can.
Thank you for the detailed responses, which have addressed my concerns. I will maintain my positive rating.
Response to Reviewer XM7d: Question 1
Thank you for the positive assessment and the constructive comments.
Response to W1 and Question 1
What Theorem 1 assumes. Only the upper bound of Theorem 1(i) uses Sc=RSR+. Theorem 1(ii) holds for every coarse operator, including the pruned one: no choice of coarse edges can bring the error at order ℓ below δℓ(π). The objective E(π) (Eq. 5) depends only on the partition and on the propagation on the full graph. So pruning does not change what the method minimizes.
The guarantee after pruning. Let Sc be the propagation operator of the pruned coarse graph, and ESc⋆(π) the constant of Definition 2 for it. The lower bound of Theorem 1 holds exactly. The upper bound holds with one additional term D (Section 3.3):
K+1E(π)≤ESc⋆(π)2≤E(π)+D(π,Sc).
This follows from Proposition 1 and Theorem 1(ii). D is the approximation error you ask about: the difference between propagation on the kept edges and the supernode averages of propagation on the full graph. So the lower bound is unchanged by pruning: the merge objective stays a floor on the error whatever edges are kept. The upper bound now includes D, which is not bounded in advance.
How significant the error is. Table 15 reports E⋆(π)2 of our coarsening with and without pruning. With pruning it is 2–10% higher (median 4.6%), and it is still lower than every baseline on all nine datasets. Downstream, accuracy with pruning is within 1 pp or better in 41 of 45 dataset–backbone pairs (Figure 3a).
Pruning is an additional step. The method does not depend on pruning. With or without pruning, our partitions have the lowest E⋆ of all methods on all nine datasets (Table 15), and the method beats most of the baselines in most of the settings. We add pruning for training cost reduction. Merging makes the coarse graph denser, and the extra edges remove most of the training speedup (Section 1, Figure 4). With pruning, training is 8× faster than on the full graph. Without it, training is 3.5× faster (Figure 2b).
The method is therefore consistent. It has one objective, its guarantee is on the partition, and pruning is an additional step that further speeds up training with accuracy mostly unaffected. Developing a pruning criterion that bounds D is an interesting direction to explore, toward a unified theory of coarsening and sparsification.