Graph Propagation under Node-Value Updates

Propagating node values across a graph is a basic operation in graph learning. We study how to maintain the result when initial input labels change but the graph and propagation rule remain fixed. Our starting point is the Friedkin–Johnsen opinion model, whose equilibrium operator is closely related to personalized PageRank and graph neural-network propagation. We start with a variation-sensitive work bound for the residual-push framework and show that it is tight up to a constant factor on unweighted graphs. We then generalize the framework from prior work to weighted graphs through a new discounted future-work potential, and further extend it to vector-valued opinions with matrix-valued couplings. Beyond opinion dynamics, our results provide a basic model of computational rollback: when a small portion of an input is discovered to be incorrect, the output can be repaired locally instead of recomputed from scratch.