We propose using homomorphism density vectors to obtain graph embeddings that are both private and expressive. Homomorphism densities are provably highly discriminative and offer a powerful tool for distinguishing non-isomorphic graphs. By adding noise calibrated to each density’s sensitivity, we ensure that the resulting embeddings sat- isfy formal differential privacy guarantees. Our construction preserves expressivity in expectation, as each private embedding remains unbiased with respect to the true homomorphism densities. We study the trade-off between privacy, utility, and expressivity, both theoretically and empiri- cally, and show that our private embeddings match the accuracy of their non-private counterparts with increased resilience to privacy attacks.