When Irrelevant Graph Growth Changes Old-Node Predictions: Graph Extension Consistency for Spectral Positional Encodings

Graph positional and structural encodings are often recomputed when an input graph grows. We ask whether this recomputation can change a frozen predictor's output on persistent nodes, even when their features, original edges, and local computational neighborhoods remain unchanged. We formalize this requirement as graph extension consistency. For global spectral encodings that retain the $k$ smallest strictly positive Laplacian modes, we identify spectral budget competition: added regions can displace modes representing the original graph. Under the stated graph and spectral-gap assumptions, we derive exact old-node spectral-projector discrepancies under disjoint extension and a strictly positive limit as a connecting bridge weakens to zero. We further introduce a paired extension audit that isolates the predictive consequences of encoding recomputation while holding learned parameters, inference state, raw features, and protected non-encoding computations fixed. Across WebKB and Airports datasets, we observe encoding-dependent probability drift and, in some configurations, prediction flips. Matched controls that preserve the original structural inputs reduce this drift to zero or the numerical-control scale, while targeted interventions distinguish spectral-input sensitivity from other encoder-domain effects. These results establish graph extension consistency as a distinct theoretical and empirical criterion for evaluating graph-dependent structural encodings.