Batch-Certified Hierarchical Spectral Transport for Efficient Domain Adaptation over Large Graphs

Graph-level domain adaptation can be expensive because it requires both acquiring structural geometry for many large graphs and optimizing transport across all source–target pairs. We introduce batch-certified hierarchical spectral transport, which estimates spectral densities only for selected anchors and allows nearby graphs to inherit explicit Wasserstein-1 uncertainty radii from graph-to-anchor certificates. For aligned graph sequences, these certificates can be constructed from sparse update lists or per-graph nuclear sparsifiers, while exceptional graphs fall back to independent estimation. At each frozen predictor round, a target-risk decomposition induces a conditional transport cost over measure-valued graph descriptors. The resulting individual cover radii define convex, mass-aware lower and upper prototype transport programs whose size depends on the number of prototypes rather than the total number of graph pairs. The upper solution can then be lifted to graph-level training weights. For entropic transport, the objective gap further bounds errors in the exact-cost plan, source weights, and weighted loss, enabling an anytime refinement procedure. The method reduces spectral computation when the graph collection admits a compact cover with tight, inexpensive certificates; in unfavorable cases, it approaches independent estimation while retaining certificate overhead. The target-risk interpretation remains conditional on calibration and representation sufficiency, and we do not claim to accelerate predictor training.