acceptodds
Under review as a conference paper at ICLR 2027

KRYLOV SUBSPACE-PRESERVING GRAPH COARSENING FOR SCALABLE GRAPH LEARNING

Abstract

Graph coarsening merges nodes into supernodes so that a graph neural network (GNN) can be trained on the smaller graph and deployed on the original. Spectral GNNs apply polynomial filters of degree at most , whose output combines the node features and their first propagations with coefficients learned only after coarsening. All such outputs lie in the span of these propagated features, the block Krylov subspace. Existing coarsening methods target the Laplacian spectrum, the topology, the node attributes or the output of one fixed convolution, and none of these criteria accounts for the full range of combinations of the propagated features. We therefore propose to preserve the Krylov subspace itself. We quantify how coarsening changes this subspace by the worst-case error of a filter learned on the coarse graph and deployed on the original. This error is bounded above and below by a -means objective on the propagated features, which we minimize by multilevel Ward merging. Many existing methods also densify the coarse graph, limiting the training speedup, and several are expensive for graphs with millions of nodes. To avoid densification, we prune edges after each level under a budget that bounds the average degree. We evaluate on nine homophilic and heterophilic node-classification benchmarks against state-of-the-art coarsening baselines, with both polynomial-filter and nonlinear GNNs. At 90% node reduction, a GCN trained on our coarse graphs is significantly more accurate than every baseline on seven of the nine datasets, with a median gain of 2.4 percentage points over the best baseline. On CPU, our coarsening method is faster than the most competitive baseline, and on one A100 GPU, our coarsening method followed by training is faster than training on the full graph.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph coarsening, graph neural networks, Krylov subspace, polynomial filters, scalable GNN training, node classification

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_XM7dOpenReview ↗
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
  1. This paper establishes meaningful bounds connecting polynomial-filter transfer errors to a tractable graph coarsening objective.

  2. 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
  1. 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?

  2. 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
AuthorsOpenReview ↗

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+S_c=RSR^{+}. Theorem 1(ii) holds for every coarse operator, including the pruned one: no choice of coarse edges can bring the error at order ℓ\ell below δℓ(π)\delta_\ell(\pi). The objective E(π)\mathcal E(\pi) (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 S~c\widetilde S_c be the propagation operator of the pruned coarse graph, and ES~c⋆(π)\mathcal E^{\star}_{\widetilde S_c}(\pi) the constant of Definition 2 for it. The lower bound of Theorem 1 holds exactly. The upper bound holds with one additional term D\mathcal D (Section 3.3):

    E(π)K+1≤ES~c⋆(π)2≤E(π)+D(π,S~c).\frac{\mathcal E(\pi)}{K+1} \le \mathcal E^{\star}_{\widetilde S_c}(\pi)^{2} \le \mathcal E(\pi)+\mathcal D(\pi,\widetilde S_c).

    This follows from Proposition 1 and Theorem 1(ii). D\mathcal 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\mathcal D, which is not bounded in advance.

  • How significant the error is. Table 15 reports E⋆(π)2\mathcal E^{\star}(\pi)^{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⋆\mathcal E^{\star} 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\mathcal D is an interesting direction to explore, toward a unified theory of coarsening and sparsification.

AuthorsOpenReview ↗

Response to Reviewer XM7d: Question 2

Response to Question 2

Thank you. We do not claim that K>1K > 1 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 K>1K > 1 helps. K>1K > 1 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 K=3K=3 against K=1K=1.

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 ∥ΓℓX∥F\lVert\Gamma_\ell X\rVert_F from the K=1K=1 to the K=3K=3 partition (%). Acc: GCN accuracy, K=3K=3 minus K=1K=1 (pp); bold: p<0.05p < 0.05 over five training seeds.

DatasetFull 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 / −10.0−1 / −1−0.1−1 / −1−0.3
igb-small−0.3−2 / −20.0−1 / −10.0+1 / +10.0

Condition (i) holds on eight of the nine datasets, so (ii) decides. Where K=1K=1 loses the most of orders 2–3 at every ratio (pokec, ogbn-products and twitch-gamers), K=3K=3 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, K=3K=3 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, K=3K=3 and K=1K=1 are indistinguishable in 18; K=3K=3 is significantly better in 8 and worse in 1 (bold in Table R3.1). Table R3.2 gives the cost of fixing KK in advance: the gap to the best KK for the same dataset and ratio.

Table R3.2. Gap to the best KK in each dataset–ratio cell (pp), mean / worst.

K=0K=0K=1K=1K=2K=2K=3K=3K=4K=4K=5K=5
All 27 cells1.33 / 6.150.79 / 5.450.57 / 5.210.26 / 1.250.18 / 0.690.30 / 1.00
Without pokec0.91 / 3.630.42 / 1.970.17 / 0.940.19 / 0.570.20 / 0.690.31 / 1.00

Every K≤2K\le 2 falls more than 5 pp below the best KK on pokec, while every K≥3K\ge 3 stays within 1.25 pp of it in all cells; without pokec, K=1K=1 still falls up to 2.0 pp below it, against 0.6 pp for K=3K=3. K=3K=3 adds at most 10 s of coarsening time over K=1K=1 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 K=3K=3, Appendix H reports E⋆(π)\mathcal E^{\star}(\pi), the largest of the per-order errors ∥ΓℓX∥F\lVert\Gamma_\ell X\rVert_F (Proposition 1). What KK changes is the error at orders 2–3, below this maximum (Table R3.1): on ogbn-products at 90%, K=3K=3 lowers the order-3 error from 0.119 to 0.101 while E⋆\mathcal E^{\star} 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.

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

This paper proposes a graph coarsening method that trains GNNs on a smaller, coarsened graph while evaluating them on the original graph. This method has several components.

Theorem 1 considers the block Krylov subspace spanned by the input features and their first KK propagations Z=[X,SX,…,SKX]Z=[X,SX,\ldots,S^KX] (along with singular value ridge rescaling and truncation), and constructs a Gram matrix UU. The coarsening operator relates to a projection Π\Pi, and this paper relates a projection-residual objective E=Tr⁡(U−ΠUΠ)E=\operatorname{Tr}(U-\Pi U\Pi) to the worst-case transfer error of a bounded class of polynomial filters (Theorem 1).

They formulate the minimization of EE as a k-means problem and adapt Ward merging (a certain multi-level hierarchical clustering method) to batched Ward merging (adding more heuristic designs) for this problem. In each level, they additionally remove merged edges to control the node degrees.

Their experiments compare the method with seven coarsening baselines on nine homophilic and heterophilic datasets using five backbones. Code is available only for the proposed method and training, but not for reproducing every figure and table.

Critical strengths
  1. A useful quantitative refinement of existing preservation analyses. The paper gives a two-sided finite-hop comparison between a projection residual and the worst-case transfer error of a bounded polynomial-filter class (Theorem 1).

  2. A practically motivated coarsening pipeline with broad evaluations. In practice, the coarsening addresses coarse-graph densification and compares the method with seven coarsening baselines on nine homophilic and heterophilic datasets using five backbones.

Critical weaknesses
  1. The incremental contribution is not sufficiently isolated from previous graph papers.

Preservation and clustering have relevant uncited references, including

  • Partition-wise Graph Filtering: A Unified Perspective Through the Lens of Graph Coarsening (KDD 2025, Theorem 3.2) already studies projected multi-step propagation
  • A Gromov-Wasserstein Geometric View of Spectrum-Preserving Graph Coarsening (ICML 2023, Section 5 and Appendix C.4.1) establishes the connection between projection-residual objectives and kernel k-means and uses the same coarse-operator construction Sc=RSR+S_c=RSR^+, with group averaging and piecewise-constant lifting. The submission's raw-trajectory objective is an instance of that kernel k-means form with the Gram matrix ZZ⊤ZZ^\top.
  • Network analysis using Krylov subspace trajectories (2024, Section 3.1) also clusters nodes using Krylov-trajectory representations.

The chosen optimizer, pruning rule, and other designs are not thoroughly justified

  • The paper doesn't explain why batched Ward merging is favored over classical Lloyd/k-means++ algorithms for k-means, wrt the objective-quality/runtime trade-off
  • For pruning, Linear-Time Multilevel Graph Partitioning via Edge Sparsification (ESA 2025) already integrate edge sparsification into multilevel graph partitioning. The submission has explicitly cited this work in Section 3.3, while we realize that sparsification between coarsening levels is already an established strategy for graphs; the methodological contribution should lie in the other components. Accordingly, whether these specific choices improve the accuracy-cost trade-off over classical edge pruning methods.
  • In Section 4.4, we see that one propagation step already recovers most of the improvement over raw-feature clustering, and that all tested K≥1K\geq1 settings are within 0.5 percentage points on the five datasets. Why would users use higher-order trajectories?
  • Rethinking Efficient Graph Coarsening via a Non-Selfishness Principle (2026, NOPE/NOPE*) is cited and listed in Table 2, but is not evaluated.
  1. [Minor] The preservation guarantee in Theorem 1 deviates from the actual method

The pruning operation and the singular value ridge rescaling and truncation are not explained by Theorem 1, though it is acknowledged in Section 3.3.

  1. The paper and released code do not consistently specify the method settings (I quote some findings below)

Absolute versus relative truncation tolerance. Appendix C.2 defines τq\tau_q as the sum of discarded ridge weights and states a default tolerance of 0.05; Appendix E.3 repeats that value. In contrast, coarsen.py:387-394 selects the retained width using (1 - tolerance) * effective_dimension, and the README describes the tolerance as a fraction of effective dimension. Thus the code uses an allowance proportional to effective dimension rather than the stated absolute allowance. These conditions can differ substantially: a controlled 100-direction identity-trajectory check with relative ridge 1e-4 retained 96 directions and discarded approximately 4.00 units of ridge energy, not at most 0.05. This is a specification discrepancy; its numerical effect on the benchmark graphs has not been established.

An undocumented-in-the-paper supernode size constraint. CoarseningConfig.size_cap defaults to 4.0. The code caps supernode size at four times the target mean size and filters adjacent candidates before calculating the reference cost for admitting non-adjacent candidates (coarsen.py:849-862, 910-911). This can change both the feasible merges and the escape threshold. Although disclosed in the README, the constraint was not identified in Section 3, Algorithms 1-2, or Appendix E.3.

Additional candidate-search differences. Algorithm 2 describes retaining the best bb candidates with neighbor-of-neighbor refinement. The implementation uses b−1b-1 searched candidates plus an independent random explorer and also injects explorer candidates during refinement (coarsen.py:524-544). This is a meaningful difference in the randomized search procedure that should be specified consistently.

A narrower implemented edge-budget range. Equation (11) permits ν≥−1\nu\geq-1 and has an additional term for negative values. The supplied configuration validator rejects negative values, and the quota function implements the nonnegative branch. This does not affect the default ν=0.3\nu=0.3, and a separate no-pruning flag exists, so it is less consequential than the discrepancies above.

  1. Inconsistent experimental records and incomplete reproduction code

The statistical summary does not consistently match its stated source table. Tables 1 and 10 mark Var-Neigh on ogbn-products at 90% reduction as OOT, and Table 15 also marks it unavailable. Table 13 nevertheless reports a +7.16-point difference for that pair and counts eight datasets in the Var-Neigh column. Table 1 contains 56 numerical dataset-baseline comparisons, whereas Appendix F states that 57 comparisons were tested. Some unavailable-result markers also change between the tables. These discrepancies require the underlying result ledger and analysis procedure to establish which comparisons actually entered the tests. They do not, by themselves, show that every reported improvement is incorrect.

The release is not an executable reproduction package for the complete empirical record. It contains the proposed coarsener, backbones and trainers, but no baseline implementations or exact baseline configurations, original run-level results, statistical-test scripts, or figure/table aggregation and rendering scripts. Data preparation is demonstrated for ogbn-arxiv/products, but complete executable preprocessing and split-selection instructions are not supplied for the remaining datasets. Bundling large datasets is not necessary; the missing acquisition-to-result instructions and analysis paths are the concern. In particular, the reported statistics and the diagnostic values of Table 15/Figure 8 cannot be regenerated directly from the supplied package.

The reported uncertainty covers only part of the method's randomness. Appendix E.2 uses a fixed coarsening with multiple training seeds. This matches the code's five-seed configurations for GCN/GraphSAGE/SIGN and three-seed configurations for SGC/GPR-GNN. However, random candidate search and allowed GPU nondeterminism can change the partition itself, and this variation is not represented by repeated training on one fixed coarse graph. The within-cell significance results therefore describe training randomness conditional on that coarsening, as Appendix F acknowledges, rather than the uncertainty of the complete method.

Questions for authors

Some questions regarding confidence in the empirical results are listed below.

  1. Evaluated implementation (Weakness 3). Which implementation and configurations generated the reported results? Please clarify whether truncation used an absolute or relative discarded-energy tolerance, whether the size cap and random explorers were active, and provide the corresponding configurations or existing run records.
  2. Statistical record (Weakness 4). Why does Table 13 include a numerical Var-Neigh/ogbn-products comparison marked OOT in Tables 1 and 10, and count 57 comparisons rather than the 56 numerical pairs in Table 1? Please provide the underlying run-level results and analysis script, and identify whether any significance conclusions change.
  3. Reproduction paths (Weakness 4). Could you provide a figure/table-level map of inputs, preprocessing and splits, method and baseline configurations, commands, and analysis scripts, particularly for Table 13 and Table 15/Figure 8? Please identify which required materials are not currently available.
7 comments
AuthorsOpenReview ↗

Response to Reviewer ZgFo: Weakness 1

Thank you for the detailed review and the constructive comments.

Response to W1: Preservation and clustering have relevant uncited references

Thank you for these references. They are relevant, and we will cite and discuss them in the revision. Our novelty and claims are different from theirs. Our core idea is to preserve the block Krylov subspace of the node features. Theorem 1 links this preservation to the worst-case error of polynomial filters, from both sides. None of the three papers uses this subspace as the criterion for coarsening. The kk-means form of the objective is a standard step and not our claim: Section 3.2 credits it to Huang et al. (2021). The core differences are as follows.

  • CPF (KDD 2025, Theorem 3.2). CPF takes its partition from an existing coarsening method and uses projected propagation to justify one filter per partition on the original graph. We use the propagated features X,SX,…,SKXX,SX,\dots,S^{K}X to choose the partition itself, because preserving them bounds the error of a filter trained on the coarse graph (Theorem 1).

  • KGC (ICML 2023). KGC preserves the Gromov–Wasserstein distance between graphs, for graph-level tasks. Its kernel is the signless Laplacian, which uses the structure only, not the node features. Our objective has the same kk-means form, like the objectives of Loukas (2019) and Huang et al. (2021). The difference is the kernel: ours is the Krylov trajectory of the node features, justified by Theorem 1.

  • Frost (2024, Section 3.1). This preprint is about network analysis. It propagates one fixed start vector with the adjacency matrix, and Section 3.1 clusters nodes by the resulting trajectories. It uses no node features. We propagate the node features and merge nodes to build a coarse graph for GNN training, with the guarantee of Theorem 1.

Response to W1: The chosen optimizer, pruning rule, and other designs are not thoroughly justified

  • Why Ward merging over Lloyd/k-means++.

    • Runtime. In coarsening, kk is a fixed fraction of nn, so classical Lloyd and standard kk-means++ seeding are quadratic in nn. Ward merging is near-linear in n+∣E∣n+|E| per level, so it scales better. None of the nine datasets needs more than 30 levels at 90% reduction (Appendix C.1).
    • Multilevel structure. Ward is bottom-up, so it has a natural multilevel structure. We prune after each level, so the final graph has fewer nodes and fewer edges (Section 3.3). This pruning can also lower the computation (Gottesbüren et al., ESA 2025).
    • Candidate pairs. Bottom-up merging lets us restrict the candidate pairs in a natural and simple way. We favor adjacent pairs and admit a non-adjacent pair only when its cost is at most a fixed fraction of the cheapest adjacent merge (Section 3.2). Lloyd ignores adjacency.
  • Pruning and edge sparsification in multilevel partitioning (ESA 2025).

    • What is new. Sparsification between levels is not our novelty. Section 3.3 cites this work, which uses it in graph partitioning. Our novelty is to show why coarsening for GNN training needs it. Merging can make the coarse graph denser, and the extra edges remove most of the training speedup (Section 1, Figure 4). We add pruning to recover this speedup. Training is 8× faster with it and 3.5× without (Figure 2b). Accuracy is within 1 pp or better in 41 of 45 dataset–backbone pairs (Figure 3a).
    • Our pruning rule. The GNN is trained on the pruned graph, so we always keep a spanning forest: pruning never disconnects a component. The edge score favors connections spread over both supernodes (Section 3.3).
    • Other sparsification methods. As you note, the core of our proposal lies in the other components: the Krylov-preserving merge criterion and its guarantee. Pruning is an additional step, so we see the comparison of sparsification methods here as an interesting direction for future work.
AuthorsOpenReview ↗

Response to Reviewer ZgFo: Weakness 1 (contd.)

Response to Weakness 1: The chosen optimizer, pruning rule, and other designs are not thoroughly justified (cont.)

Why higher-order trajectories (K>1K > 1).

Thank you. We do not claim that K>1K > 1 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 K>1K > 1 helps. K>1K > 1 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 K=3K=3 against K=1K=1.

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 ∥ΓℓX∥F\lVert\Gamma_\ell X\rVert_F from the K=1K=1 to the K=3K=3 partition (%). Acc: GCN accuracy, K=3K=3 minus K=1K=1 (pp); bold: p<0.05p < 0.05 over five training seeds.

DatasetFull 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 / −10.0−1 / −1−0.1−1 / −1−0.3
igb-small−0.3−2 / −20.0−1 / −10.0+1 / +10.0

Condition (i) holds on eight of the nine datasets, so (ii) decides. Where K=1K=1 loses the most of orders 2–3 at every ratio (pokec, ogbn-products and twitch-gamers), K=3K=3 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, K=3K=3 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, K=3K=3 and K=1K=1 are indistinguishable in 18; K=3K=3 is significantly better in 8 and worse in 1 (bold in Table R3.1). Table R3.2 gives the cost of fixing KK in advance: the gap to the best KK for the same dataset and ratio.

Table R3.2. Gap to the best KK in each dataset–ratio cell (pp), mean / worst.

K=0K=0K=1K=1K=2K=2K=3K=3K=4K=4K=5K=5
All 27 cells1.33 / 6.150.79 / 5.450.57 / 5.210.26 / 1.250.18 / 0.690.30 / 1.00
Without pokec0.91 / 3.630.42 / 1.970.17 / 0.940.19 / 0.570.20 / 0.690.31 / 1.00

Every K≤2K\le 2 falls more than 5 pp below the best KK on pokec, while every K≥3K\ge 3 stays within 1.25 pp of it in all cells; without pokec, K=1K=1 still falls up to 2.0 pp below it, against 0.6 pp for K=3K=3. K=3K=3 adds at most 10 s of coarsening time over K=1K=1 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 K=3K=3, Appendix H reports E⋆(π)\mathcal E^{\star}(\pi), the largest of the per-order errors ∥ΓℓX∥F\lVert\Gamma_\ell X\rVert_F (Proposition 1). What KK changes is the error at orders 2–3, below this maximum (Table R3.1): on ogbn-products at 90%, K=3K=3 lowers the order-3 error from 0.119 to 0.101 while E⋆\mathcal E^{\star} rises from 0.430 to 0.460. A maximum over orders cannot show this; the per-order errors can.

NOPE is not evaluated. We have now run NOPE*, the faster variant of NOPE, under the protocol of Table 1 (90% reduction, GCN, five training seeds, six-hour limit).

DatasetNOPE*Ours
igb-small70.18 ± 0.0471.82 ± 0.03
ogbn-arxiv64.01 ± 0.5968.93 ± 0.11
ogbn-mag27.56 ± 0.6035.11 ± 0.19
ogbn-products61.76 ± 0.8676.43 ± 0.20
reddit292.01 ± 0.0593.55 ± 0.05
arxiv-year39.13 ± 0.3240.62 ± 0.18
pokecout of time (> 6 h)58.47 ± 1.03
snap-patents31.02 ± 0.4234.71 ± 0.22
twitch-gamers59.59 ± 0.2561.54 ± 0.13

Our method is more accurate on all eight datasets on which NOPE* finishes, by 1.5 to 14.7 pp.

AuthorsOpenReview ↗

Response to Reviewer ZgFo: Weakness 2 and 3

Response to W2

  • Ridge scaling and truncation. Theorem 1 holds for every partition, so it applies to the partition that the actual method outputs. Appendix C.2 relates both steps to the objective of Theorem 1 (Eq. 17 and Eq. 18).

  • Pruning. The objective E(π)\mathcal E(\pi) depends only on the partition and on the propagation operator of the full graph. The edges of the coarse graph do not appear in it, so pruning cannot change what the method minimizes. Pruning also does not remove the guarantee completely. For the pruned operator S~c\widetilde S_c and its constant ES~c⋆\mathcal E^{\star}_{\widetilde S_c} (Definition 2), the lower bound of Theorem 1 holds unchanged, and the upper bound holds with one additional term D\mathcal D (Section 3.3):

    E(π)K+1≤ES~c⋆(π)2≤E(π)+D(π,S~c).\frac{\mathcal E(\pi)}{K+1} \le \mathcal E^{\star}_{\widetilde S_c}(\pi)^{2} \le \mathcal E(\pi)+\mathcal D(\pi,\widetilde S_c).

    This follows from Proposition 1 and Theorem 1(ii). The effect of pruning on E⋆\mathcal E^{\star} is small, as Table 15 shows, and accuracy is mostly unaffected (Figure 3a). Developing a pruning criterion that bounds D\mathcal D is an interesting direction to explore.

In practice, the partitions that the full method outputs have the lowest E⋆\mathcal E^{\star} of all methods on all nine datasets (Table 15).

Response to W3

Truncation tolerance. The released code is correct, and all results of our method in the paper were produced by it. The tolerance is relative: with the default 0.05, we keep the smallest width qq with τq≤0.05deff\tau_q\le 0.05 d_{\mathrm{eff}}, as the README states. The submitted Appendices C.2 and E.3 stated the value 0.05 without the factor deffd_{\mathrm{eff}}. We have updated both in the revision: they now state τq≤0.05deff(λ)\tau_q\le 0.05 d_{\mathrm{eff}}(\lambda). Eq. 18 holds for any qq, so the bound is unchanged.

Size cap. All results in the paper use a supernode size cap of 4n/k4n/k, as in the released code and its README. The cap is an implementation safeguard: no supernode may exceed four times the mean size n/kn/k. We have added it to the revision as Appendix I. We also evaluated the method without the cap (GCN, 90% reduction; Table 16 in Appendix I):

DatasetCap 4 (paper)No cap
igb-small71.82 ± 0.0371.76 ± 0.05
ogbn-arxiv68.93 ± 0.1168.84 ± 0.17
ogbn-mag35.11 ± 0.1935.01 ± 0.30
ogbn-products76.43 ± 0.2075.65 ± 0.30
reddit293.55 ± 0.0592.49 ± 0.17
arxiv-year40.62 ± 0.1840.64 ± 0.19
pokec58.47 ± 1.0358.53 ± 0.50
snap-patents34.71 ± 0.2234.61 ± 0.17
twitch-gamers61.54 ± 0.1361.50 ± 0.18

Accuracy is within 0.1 pp on seven datasets. Without the cap it is lower on ogbn-products and Reddit2, by 0.8 and 1.1 pp.

Candidate search. The released code is correct, and all results in the paper are consistent with it. The code keeps the b−1b-1 cheapest candidates and adds one random supernode, the explorer. This is a small implementation heuristic. We omitted it from Algorithm 2 to present the core idea of the search in a simple way. Each supernode still has bb candidates, and the explorer must pass the same ζ\zeta test as every other non-adjacent candidate. We have already updated Algorithm 2 in the revision to include it.

Edge budget. As you note, this does not affect the default ν\nu. It also does not affect any result, analysis or idea in the paper: every reported run uses ν≥0\nu\ge 0, and the runs without pruning use the separate flag, which is the case ν=−1\nu=-1. Adding the branch −1≤ν<0-1\le\nu < 0 of Eq. 11 is a small code change, and we will include it in the revised version.

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

This paper proposes a graph coarsening method for linear polynomial-filter GNNs, designed to preserve the block Krylov subspace of the node features.

Critical strengths

S1. The paper defines the error incurred by the merge operation, establishes its error-bound properties, and proposes a greedy graph coarsening method based on Ward agglomeration.

S2. The experimental evaluation covers a wide range of GNNs, including nonlinear ones. It verifies that the proposed method speeds up end-to-end GNN training and improves the accuracy of many GNNs over state-of-the-art graph coarsening methods.

Critical weaknesses

W1. Consistency of the method.

  • As the authors themselves acknowledge in their discussion of future work, “the guarantee covers node merging alone, and edge pruning is applied after it without a bound of its own.” The error minimization in the merging step and the edge reduction are designed separately, so it is not clear what the proposed method minimizes as a whole.
  • The guarantee of Krylov subspace preservation is discussed only for node merging. Edge reduction falls outside the scope of this guarantee, which makes the overall design of the method appear inconsistent.

W2. As Figure 2 shows, the method achieves a substantial speedup in GNN training. However, as Table 1 shows, graph coarsening degrades GNN accuracy compared with training on the full graph. From a user’s perspective, the goal is to optimize the trade-off between accuracy and running time. Tables 9-12 analyze the effect of varying the reduction ratio, but the paper does not go as far as discussing how to optimize this trade-off.

Questions for authors

No questions.

3 comments
AuthorsOpenReview ↗

Response to Reviewer ro6A

Thank you for the positive assessment and the constructive comments. We address both weaknesses below.

Response to W1

  • What the method minimizes as a whole. One objective, E(π)\mathcal E(\pi) (Eq. 5). It measures how much of the propagated features X,SX,…,SKXX,SX,\dots,S^{K}X is lost when nodes are merged. It needs only the partition and the propagation operator of the full graph. The operator and the edges of the coarse graph do not appear in it. So pruning cannot change what the method minimizes. It changes only which pairs are candidates for the next merge.

  • Why we prune. Pruning is an additional step, and its purpose is 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). Accuracy is mostly unaffected (Figure 3a). The method also works without pruning: it is still faster than the strongest baseline and beats most of the baselines in most of the settings.

  • The guarantee after pruning. Pruning does not remove the guarantee completely. Let S~c\widetilde S_c be the propagation operator of the pruned coarse graph. The lower bound of Theorem 1 holds unchanged. The upper bound holds with one additional term D\mathcal D (Section 3.3):

    E(π)K+1≤ES~c⋆(π)2≤E(π)+D(π,S~c).\frac{\mathcal E(\pi)}{K+1} \le \mathcal E^{\star}_{\widetilde S_c}(\pi)^{2} \le \mathcal E(\pi)+\mathcal D(\pi,\widetilde S_c).

    This follows from Proposition 1 and Theorem 1(ii). The effect of pruning on E⋆\mathcal E^{\star} is small, as Table 15 shows. What remains open is one specific point: D\mathcal D is not bounded in advance and depends on the propagation operator of the coarsened graph. Our edge rule keeps the graph sparse, but it is not yet derived from D\mathcal D. A method that selects nodes and edges under one objective, E+D\mathcal E+\mathcal D, would close this gap and unify coarsening and sparsification.

The method is therefore consistent: it has one objective, and pruning is an additional step that speeds up training with accuracy mostly unaffected. Developing a pruning criterion that bounds D\mathcal D is an interesting direction to explore, toward a unified theory of coarsening and sparsification.

Response to W2

  • Accuracy–time trade-off. This is an interesting question for the field. It applies to every coarsening method, not only to ours. Our paper asks a different question: at a fixed budget, which coarsening gives the best coarse graph for the downstream task (node classification). Like the baselines, our method takes the target size kk as input (Section 3), and Tables 9–12 compare the methods at four fixed budgets. Optimizing the trade-off between accuracy and running time is a separate problem. We see it as a promising direction for future work.
AuthorsOpenReview ↗

Gentle follow-up request on our rebuttal / response

Dear Reviewer ro6A,

Thank you again for your time and thoughtful feedback on our submission. We wanted to send a gentle follow-up to ensure our earlier response addressed your main concerns.

As the discussion period is nearing its end, we would greatly appreciate any further thoughts or feedback you might have, or knowing whether our clarifications have resolved your concerns. We remain happy to provide any additional details if needed.

Thank you very much for your consideration.

Best regards,

Authors

Thank you for all your responses: they are reasonable and mostly for the future work. I keep my positive evaluation score.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Response summary for Reviewers and Area Chairs

We thank the reviewers for their time and for their careful and constructive reviews. Their comments helped us present our work more clearly, and they also pointed us to some interesting directions for future work. Here is a short summary of our responses.

  • Reviewer ro6A: Our method has one objective, and it does not depend on the edges of the coarse graph. Pruning is an additional step that makes training faster (8× instead of 3.5×) with accuracy mostly unaffected. After pruning, the lower bound of Theorem 1 still holds, and the upper bound holds with one extra term. Optimizing the accuracy–time trade-off is a separate problem, which we see as future work.

  • Reviewer ZgFo: The detailed feedback helped us make the revised paper clearer. The revision now includes the implementation details that were missing: the relative truncation tolerance, the supernode size cap and the random explorer in the candidate search. We also explained how our core idea differs from the three suggested papers, which we will cite. We showed results for NOPE*: our method is more accurate on all eight datasets on which NOPE* finishes. We also ran our method end to end with five seeds, and the results stay close to Table 1.

  • Reviewer XM7d: Only the upper bound of Theorem 1 assumes Sc=RSR+S_c=RSR^{+}. The lower bound also holds for the pruned operator, and the effect of pruning on the error is small (Table 15). For higher orders, we show that a larger KK lowers the error at the higher orders. Appendix H does not show this, because it reports the maximum over orders and not the per-order errors.

We hope these responses address the reviewers' concerns, and we are happy to answer any further questions.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.