Multiton implementation for frozensets

How can I implement the Multiton design pattern for frozensets, in a way which works no matter how the frozenset is created?

Basically, what I'm looking for is class that behaves just like frozenset, but that gaurantees "full interning": for any two instances, if a == b then a is b.

The answers to this question seem to produce a single instance for every argument passed to the constructor (and also seem to assume that these are hashable). But a given frozenset may be constructed in many different ways: the constructor may get tuples with different ordering of the elements, or unhashable lists; or you might use some operator such as a.union(b) to create the frozenset, etc.

The motivation is, naturally - trying to save memory. I have a graph with many vertices labeled by (among other things) recurring frozensets. The graph is "grown" by creating new vertices from old, and the new frozensets are obtained by adding or removing elements from the old ones.

Many thanks!