Learning After Structural Poisoning: Label Coverage and Label Transfer

Structural poisoning can erase target information without destroying realizability; labels can recover this information, yet training may fail to transfer it. On a sparse-tree family, we derive an exact coverage-based minimax law and a depth-dependent capacity law. A separate connected, bounded-degree construction preserves the realizing teacher under legal edge additions and has 20% cross-block neighbor-message mass at receivers. On this family, we prove a nonvanishing expected excess-risk lower bound over the information reference for finite-width, one-hop nonlinear graph neural networks with shared representations and trainable biases. The bound holds for GD and Adam at every fixed training horizon under the specified independent initialization and equally weighted hit-role logistic loss. A permutation symmetry obstructs label transfer even when cross-role logit-gradient inner products remain strictly positive. In a linear specialization, a positive-definite gradient preconditioner attains the information reference in one step without changing the function class, loss, or initial predictor. In a matched nonlinear study on the connected family, coupled Adam updates reduce overall test error by 10.90 percentage points across 96 independent problems, with all observed labels fitted. These results establish a separation between label coverage and label transfer, and show how optimizer design can improve transfer within a fixed model class.