Successful Constraint Optimization Need Not Certify Structural Fidelity: A Verification Gap in Graph Structure Learning

Graph structure learning methods often adapt graph structure from data while incorporating predefined graphs, structural priors, or constraint-based objectives. When a learned graph is claimed to realize a specific external structural target, however, optimization success raises a separate verification question: do the optimized and reported quantities actually certify fidelity to that target? We study this question in a controlled declared-target setting. An external graph \(A^*\) guides a warmup phase; thereafter, the main non-oracle training arms continue without allowing \(A^*\) to influence graph updates, while \(A^*\) is retained for structural audit. Within the Hinge runs on the primary traffic networks, the residual proxy decreases by more than 98% from the warmup boundary and approaches zero. At the final epoch, paired Hinge–ReLU task-error differences remain small, whereas evaluation-only structural audits show lower target fidelity under Hinge than under ReLU. This lower-target-fidelity pattern replicates across four amortized graph learners and multiple traffic networks. We further characterize when surrogate near-optimality can certify proximity to the declared target and isolate two distinct failure points: the constraint interface may lack sufficient target-discriminating information, or the realized graph updates may move in a structurally unfavorable direction. An \(A^*\)-dependent oracle gradient intervention consistently improves local structural quantities but does not reliably restore global edge ranking. This recovery boundary motivates limiting post-warmup deviation from a high-fidelity warmup anchor without requiring \(A^*\) for subsequent non-oracle updates. The resulting guardrail substantially limits structural drift relative to unconstrained continued training; under a controlled fixed-support shift, it retains more structural fidelity than unconstrained adaptation while adapting better than freezing. Thus, task-side behavior and successful surrogate optimization do not, by themselves, certify fidelity to a declared external target. Such claims require direct structural evidence or a demonstrated certificate linking the reported quantities to that target.