I uploaded some photos to Google photos that were taken by a very old digital camera that does not have GPS or location capability. Yet Google photos was able to determine correct city in which the photo was taken. In some cases it also determined the approximate place where it was taken. How does it do that?
They can use machine learning to guess location from photo
Guessing the location of a randomly chosen Street View image is hard, even for well-traveled humans. But Google’s latest artificial-intelligence machine manages it with relative ease. [...] “PlaNet is able to localize 3.6 percent of the images at street-level accuracy and 10.1 percent at city-level accuracy,” say Weyand and co. What’s more, the machine determines the country of origin in a further 28.4 percent of the photos and the continent in 48.0 percent of them.
Confirmed by uploading the sphinx picture (from wikipedia) with all EXIF information removed. After a while, the location was automatically changed to "Giza Necropolis". Obviously this information can't come from GPS, phone spying or timestamp matching and could only be derived from the photograph itself.
So, the good news is, google knowing the location of your photos does not necessarily mean you are being tracked without your permission. Your location can be seen because you are showing the location in your photos!
I wasn't carrying any smartphone with me when I took those photographs. I did occasionally login to my Google account on a smartphone when I was there. The photos however were uploaded a few weeks afterwards and from a desktop.
It doesn't matter when you upload them or from where you uploaded them. Unless the images have had their EXIF info stripped before you uploaded them, Google is smart enough to read that information from the photos and determine when they were taken.
Next it compares the time stamp in the images to your known locations based on your google logins. It finds your logins that were closest, timewise, to when the photos were taken. Now it knows approximately where you were when the photos were taken. At the very least it can narrow down where you might have been within a certain range of travel. From there it is able to begin searching its vast database to find similar scenes in the same areas.