A computer program product is provided for fault diagnostics and recovery of network service chains. The product includes a computer readable storage medium having program instructions embodied therewith. The program instructions are executable by a computer to cause the computer to perform a method. The method includes identifying intersecting ones of components of the network service chains in a network graph indicative of a commonality therebetween. The method further includes selectively repairing one or more of the components of at least one of the network service chains up to an entirety thereof based on a component repair sequence that maintains service continuity of the network service chains and that is determined and selectively reordered based on the commonality. The network graph includes a plurality of graphs, each (i) including one or more Virtualized Network Functions, and (ii) corresponding to a respective one of the network service chains.