Certified End-to-End Graph-Induced Surrogate Compression for Black-Box Local Intervention
Desk rejected at ICLR 2027, so left out of the paper lists and the map.
Abstract
In expensive graph intervention, the search domain is often not designed by the optimizer. A cheap graph heuristic or learned front end proposes a shortlist, and a black-box optimizer then spends simulator calls inside that domain. This fixed-domain view hides the central risk: the shortlist may be simple enough to compress, or it may be missing the edits that matter. Returning to the full library exposes this risk but destroys the simulator-call budget. We formulate the missing layer as auditable post-screening: the system returns not only a deployment, but also queried interactions, surrogate fit, omitted-candidate risk, and a deploy / expand / enrich / fallback recommendation. Local footprints induce a shortlist interaction graph; clique queries and Möbius inversion recover a graph-induced surrogate whose query complexity is controlled by local overlap and bag load rather than ambient library size. Outside, joint, and sparse-clique certificates turn residual shortlist risk into one-sided measurable quantities. The practical system is pairwise, with general-order theory as the structural query template; on moderate real tasks and localized large graphs, it reaches high-call greedy references in the main giant-connected-component (GCC) rows using up to about 70% fewer simulator calls, while the same run records shortlist credibility, certificate evidence, and next-call repair decisions under the charged budget.
- Primary area:
- learning on graphs and other geometries & topologies