KRYLOV SUBSPACE-PRESERVING GRAPH COARSENING FOR SCALABLE GRAPH LEARNING

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 $K$, whose output combines the node features and their first $K$ 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 $k$-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 $3\times$ faster than the most competitive baseline, and on one A100 GPU, our coarsening method followed by training is $5\times$ faster than training on the full graph.