User interface for excluding tags from a selection

I'm working on a photo-management application.

One way users can organize photos is by tagging them: free-form tagging with autocomplete. In the interest of ease of use, I've put almost no restrictions on tag names: anything you can type, you can use in a name.

Interaction with tags, other than applying them, is through GUI elements. For example, filtering by tag is done through a list of all tags. If the user wants to view all items tagged as fire hydrant, they simply click on that tag in the list. If they want to limit it to fire hydrants in Portland, Maine, they can scroll down to the Portland, Maine tag and shift-click it.

How would I implement tag exclusion here? If the user wants all images of fire hydrants in Portland, Maine except those with dogs nearby, they scroll up to dog and...do what?

I'd like to preserve right-clicking as a way to bring up a context menu with operations on tags (such as deleting or renaming them). As noted above, tag names are free-form, so any text-based filter language will come with arcane character-escaping rules, which is counter to the ease of use I'm trying for. I figure that "excludes" filtering will be a far less common operation than "and" filtering, so any solution should avoid making "and" harder to use.