COST-GED: COST-VALIDATED SELF-IMPROVEMENT FOR GRAPH EDIT DISTANCE

Graph edit distance (GED) is a fundamental measure of graph similarity, but computing it exactly is NP-hard. Although neural GED solvers improve inference efficiency, many still rely on exact GED values or optimal matchings as supervision, limiting large-scale training, especially on graphs with complex node and edge labels. We introduce COST-GED, a cost-validated self-improvement framework that requires neither exact GED values nor optimal matchings as training supervision. COST-GED exploits the fact that the edit cost of a feasible matching can be computed directly and provides an upper bound on GED. It updates pseudo-matchings using edit costs rather than model confidence: a candidate is accepted only if it strictly lowers the current cost, and the improved matching supervises an autoregressive solver. For each fixed graph pair and edit-cost function, this rule guarantees a monotonically non-increasing pseudo-matching cost. Global sampling and local perturbation-based reconstruction balance exploration with reuse of existing correspondences. Across six public small-graph GED benchmarks, COST-GED achieves performance competitive with supervised methods. On Code2-22, increasing the unlabeled training pool from 2K to 40K graph pairs improves the exact hit rate (EHR) from 84.5% to 95.8%. On the larger MolHIV-30-50 and MolHIV-50-70 benchmarks, COST-GED reduces the mean edit cost of returned feasible matchings by 16.92% and 19.26%, respectively, relative to IPFP, the best-performing traditional baseline in our comparison.