A method includes configuring services as respective collections of subservices on network devices of a network, and decomposing definitions of the services into subservice dependency graphs each indicating the subservices and dependencies between the subservices that collectively implement a respective one of the services. The method further includes traversing the subservice dependency graphs to identify, at one or more intersections of the subservice dependency graphs, one or more shared subservices among the subservices of the services, wherein the one or more shared subservices are shared by the services. The method also includes monitoring subservice health states of the one or more shared subservices, and determining health states of the services based on the subservice health states of the one or more shared subservices.