Recent research has identified interactions between networks as crucial for the outcome of evolutionary games taking place on them. While the consensus is that interdependence does promote cooperation by means of organizational complexity and enhanced reciprocity that is out of reach on isolated networks, we here address the question just how much interdependence there should be. Intuitively, one might assume the more the better. However, we show that in fact only an intermediate density of sufficiently strong interactions between networks warrants an optimal resolution of social dilemmas. This is due to an intricate interplay between the heterogeneity that causes an asymmetric strategy flow because of the additional links between the networks, and the independent formation of cooperative patterns on each individual network. Presented results are robust to variations of the strategy updating rule, the topology of interdependent networks, and the governing social dilemma, thus suggesting a high degree of universality.