As far as I am aware digging is a very natural habit for all dogs (some species more than others). Dogs dig burrows/dens to shade from the sun, shelter from the cold and raise pups etc.
We have avoided the garden excavation by allowing Kelso to have her own where digging is permitted (although sometimes the area we want her to dig in and the area she wants to dig in don't match). We bury her toys in this area and sometimes even treats so that if we are not there to praise her she is still being positively reinforced.
Other suggestions i have had (but never put into practice) is to put the dogs poo in the holes you don't want them to dig again or bury water balloons which will burst and frighten them. Also a guy I know with a Malamute used tabasco sauce on eggshells!
Good luck