We evaluate the nonlinear coefficient of graphene-on-silicon waveguides through the coincidence measurement of photon-pairs generated via spontaneous four-wave mixing. We observed the temporal correlation of the photon-pairs from the waveguides over various transfer layouts of graphene sheets. A simple analysis of the experimental results using coupled-wave equations revealed that the atomically-thin graphene sheets enhanced the nonlinearity of silicon waveguides up to ten-fold. The results indicate that the purely $chi^{(3)}$-based effective nonlinear refractive index of graphene is on the order of $10^{-13}$ m$^2$/W, and provide important insights for applications of graphene-based nonlinear optics in on-chip nanophotonics.