We study solution sensitivity for nonlinear programs (NLPs) whose structure is induced by a graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$. These graph-structured NLPs arise in many applications such as dynamic optimization, stochastic optimization, optimization with partial differential equations, and network optimization. We show that the sensitivity of the primal-dual solution at node $i\in \mathcal{V}$ against a data perturbation at node $j\in \mathcal{V}$ is bounded by $\Upsilon \rho^{d_\mathcal{G}(i,j)}$ for constants $\Upsilon>0$ and $\rho\in(0,1)$ and where $d_\mathcal{G}(i,j)$ is the distance between $i$ and $j$ on $\mathcal{G}$. In other words, the sensitivity of the solution decays exponentially with the distance to the perturbation point. This result, which we call exponential decay of sensitivity (EDS), holds under fairly standard assumptions used in classical NLP sensitivity theory: the strong second-order sufficiency condition and the linear independence constraint qualification. We also present conditions under which the constants $(\Upsilon,\rho)$ remain uniformly bounded; this allows us to characterize behavior for NLPs defined over subgraphs of infinite graphs (e.g., as those arising in problems with unbounded domains). Our results provide new insights on how perturbations propagate through the NLP graph and on how the problem formulation influences such propagation. Specifically, we provide empirical evidence that positive objective curvature and constraint flexibility tend to dampen propagation. The developments are illustrated with numerical examples.