We consider the mass-critical non-linear Schrödinger equation on non-compact metric graphs. A quite complete description of the structure of the ground states, which correspond to global minimizers of the energy functional under a mass constraint, is provided by Adami, Serra and Tilli in [R. Adami, E. Serra and P. Tilli. Negative energy ground states for the L2-critical NLSE on metric graphs. Comm. Math. Phys. 352 (2017), 387–406.] , where it is proved that existence and properties of ground states depend in a crucial way on both the value of the mass, and the topological properties of the underlying graph. In this paper we address cases when ground states do not exist and show that, under suitable assumptions, constrained local minimizers of the energy do exist. This result paves the way to the existence of stable solutions in the time-dependent equation in cases where the ground state energy level is not achieved.