Q:

What is an efficient way to exchange the order of keys in nested dictionaries in Python? 

Apologies for the convoluted question title, but here's an example of what I mean. 
Transform
mydictionary = {"OuterKey1": {"InnerKey1": "Value1", "InnerKey2": "Value2"}, 
                "OuterKey2": {"InnerKey1": "Value3", "InnerKey2": "Value4"}}

into
newdictionary = {"InnerKey1" : {"OuterKey1" : "Value1", "OuterKey2" : "Value3"},
                 "InnerKey2" : {"OuterKey1" : "Value2", "OuterKey2" : "Value4"}}

Notice how the association of InnerKey,OuterKey pair to values is preserved, but their order has simply been reversed.  Where we would previously access Value1 using mydictionary[OuterKey][InnerKey] we now access it using newdictionary[InnerKey][OuterKey]. 
A direct way to achieve this would be to recreate two nested loops through the first dictionary and build the second dictionary one element at a time.  
However, I wonder if there's a cleaner / more Pythonic way to do it, such as with list comprehensions. 
Update: It seems there is some confusion about the desired output.  In particular, there is confusion about which value an OuterKey should map to after the tranformation. 
The answer is that the former outer key (now inner key) should map to the same value that the former inner key (now outer key) mapped to. 

A:

In this case I find using setdefault in a loop (or a defaultdict) much more readable then a comprehension.  After all, "Readability counts...":
mydictionary = {"OuterKey1": {"InnerKey1": "Value1", "InnerKey2": "Value2"}, "OuterKey2": {"InnerKey1": "Value3", "InnerKey2": "Value4"}}
d = {}
for k, v in mydictionary.items():
    for ik, iv in v.items():
            d.setdefault(ik, {})[k] = iv

# result:
# d == {'InnerKey2': {'OuterKey2': 'Value4', 'OuterKey1': 'Value2'}, 'InnerKey1': {'OuterKey2': 'Value3', 'OuterKey1': 'Value1'}}

The same using defaultdict:
from collections import defaultdict
d = defaultdict(dict)
for k, v in mydictionary.items():
    for ik, iv in v.items():
            d[ik][k] = iv

