Summary: Let \({\mathcal G}\) be a simple countable connected graph and let \(H_0\) be the discrete Laplacian on \(l^2({\mathcal G})\). Let \(\Gamma\subset{\mathcal G}\) and let \(V= \sum_{n\in\Gamma} V(n)(\delta_n|\cdot)\delta_n\) be a potential supported on \(\Gamma\). We study scattering properties of the operators \(H= H_0+V\). Assuming that the wave operators \(W^\pm(H,H_0)\) exist, we find sufficient and necessary conditions for their completeness in terms of a suitable criterion of localization along the subspace \(l^2(\Gamma)\). We discuss the case of random subspace potentials, for which these conditions are particularly natural and effective. As an application, we discuss scattering theory of the discrete Laplacian on the half-space \({\mathcal G}=\mathbb Z^d\times\mathbb Z_+\) perturbed by a potential supported on the boundary \(\Gamma=\mathbb Z^d\times\{0\}\).