We demonstrate the existence of Giant proximity magnetoresistance (PMR) effect in a graphene spin valve where spin polarization is induced by a nearby magnetic insulator. PMR calculations were performed for yttrium iron garnet (YIG), cobalt ferrite (CFO), and two europium chalcogenides EuO and EuS. We find a significant PMR (up to 100%) values defined as a relative change of graphene conductance with respect to parallel and antiparallel alignment of two proximity induced magnetic regions within graphene. Namely, for high Curie temperature (Tc) CFO and YIG insulators which are particularly important for applications, we obtain 22% and 77% at room temperature, respectively. For low Tc chalcogenides, EuO and EuS, the PMR is 100% in both cases. Furthermore, the PMR is robust with respect to system dimensions and edge type termination. Our findings show that it is possible to induce spin polarized currents in graphene with no direct injection through magnetic materials.