Finite Teaching, Infinite Horizons: Sharp Guarantees for Min-Aggregation

We show when errors on a small teaching set certify a learned graph algorithm on unseen graphs and at arbitrary execution lengths. For nonnegative, bias-free min-aggregation networks of arbitrary width, we compute the exact worst-case relative error against Bellman–Ford from the weights alone. Just $K+2$ labeled endpoints identify exact $K$-step execution. With normalized mixing and bounded edge coefficients, their teaching error equals the global error. For shared networks with fixed normalized connections, we determine the optimal error amplification over all execution lengths. It is finite exactly when teaching exposes every eventually observable channel. This factor also guides readout design. For irreducible connections with $q$ message channels, an optimized readout achieves one-step amplification within a factor $1+1/q$ of optimal. Matching hitting and propagation bounds certify multi-step optimality. In three paired fits, adding one teaching graph reduces global errors initially between 19.92% and 47.99% to below 0.163% in every case.