Large spin-orbital proximity effects have been predicted in graphene interfaced with a transition metal dichalcogenide layer. Whereas clear evidence for an enhanced spin-orbit coupling has been found at large carrier densities, the type of spin-orbit coupling and its relaxation mechanism remained unknown. We show for the first time an increased spin-orbit coupling close to the charge neutrality point in graphene, where topological states are expected to appear. Single layer graphene encapsulated between the transition metal dichalcogenide WSe$_2$ and hBN is found to exhibit exceptional quality with mobilities as high as 100000 cm^2/V/s. At the same time clear weak anti-localization indicates strong spin-orbit coupling and a large spin relaxation anisotropy due to the presence of a dominating symmetric spin-orbit coupling is found. Doping dependent measurements show that the spin relaxation of the in-plane spins is largely dominated by a valley-Zeeman spin-orbit coupling and that the intrinsic spin-orbit coupling plays a minor role in spin relaxation. The strong spin-valley coupling opens new possibilities in exploring spin and valley degree of freedom in graphene with the realization of new concepts in spin manipulation.