Entanglement entropy in a field theory, with a holographic dual, may be viewed as a quantity which encodes the diffeomorphism invariant bulk gravity dynamics. This, in particular, indicates that the bulk Einstein equations would imply some constraints for the boundary entanglement entropy. In this paper we focus on the change in entanglement entropy, for small but arbitrary fluctuations about a given state, and analyze the constraints imposed on it by the perturbative Einstein equations, linearized about the corresponding bulk state. Specifically, we consider linear fluctuations about BTZ black hole in 3 dimension, pure AdS and AdS Schwarzschild black holes in 4 dimensions and obtain a diffeomorphism invariant reformulation of linearized Einstein equation in terms of holographic entanglement entropy. We will also show that entanglement entropy for boosted subsystems provides the information about all the components of the metric with a time index.