We propose a novel framework for constructing and computing various stable network observables. Our approach is based on sampling a random homomorphism from a small motif of choice into a given network. Integrals of the law of the random homomorphism induces various network observables, which include well-known quantities such as homomorphism density and average clustering coefficient. We show that these network observables are stable with respect to renormalized cut distance between networks. For their efficient computation, we also propose two Markov chain Monte Carlo algorithms and analyze their convergence and mixing times. We demonstrate how our techniques can be applied to network data analysis, especially for hypothesis testing and hierarchical clustering, through analyzing both synthetic and real world network data.