Contrary to what a lot of people think, you can change the visibility of likes. This affects Graph Search, Timeline visibility, and also page visibility (I've personally tested these). The Admins of pages you like will still be able to see that you like their page.
Go to the Likes page on your timeline. Click the Edit button in the upper right. Privacy visibility buttons will pop up next to each Like category for you to change the visibility of Likes. Make sure to scroll down to the bottom so you don't miss the last category "Other Pages You Like."
Yes, Facebook intentionally doesn't do a good job of advertising this. For me, though, I'm satisfied that the option is there (and that my option to stalk my friends is there as well).
I appreciate the information, but this misses the point. Facebook hides privacy settings because privacy is bad for their business objectives, and most people will never bother to dig for these settings, leaving them open to the kinds of attacks demonstrated by the original post.
Chart me a path from the privacy settings dialog in the header to changing the visibility of individual "likes", such that the average user can prepare to hide from random strangers when Open Graph Search goes public.
Yes, but one of those searches was for family members of people who supported the Falun Gong. You may live in the US, be a member of the Falun Gong and your grandparents in China get picked up and shipped off for suspected support.
Even if the privacy settings do allow you to opt out of being visible in Graph Search (and there is an open question of if it would for a query that returns other people instead of you), now people's safety is involved for something they themselves have no control over.