Mean-field approximations (MFAs) are frequently used in physics. When a process (such as an epidemic or a synchronization) on a network is approximated by MFA, a major hurdle is the determination of those graphs for which MFA is reasonably accurate. Here, we present an accuracy criterion for Markovian susceptible-infected-susceptible (SIS) epidemics on any network, based on the spectrum of the adjacency and SIS covariance matrix. We evaluate the MFA criterion for the complete and star graphs analytically, and numerically for connected Erd?s-Rényi random graphs for small size N?14. The accuracy of MFA increases with average degree and with N. Precise simulations (up to network sizes N=100) of the MFA accuracy criterion versus N for the complete graph, star, square lattice, and path graphs lead us to conjecture that the worst MFA accuracy decreases, for large N, proportionally to the inverse of the spectral radius of the adjacency matrix of the graph.