Unintentional mutable default arguments lead to surprising results and are confusing to newcomers to say the least ( https://docs.python-guide.org/writing/gotchas ).

A mutable default argument

def __init__(self, attrs={}):
    self.attrs = attrs

can be replaced with

def __init__(self, attrs=None):
    self.attrs = {} if attrs is None else attrs

or possibly even more compact

def __init__(self, attrs=None):
    self.attrs = attrs or {}

However, this particular exercise forces all of the arguments to be passed through the test suite (specifically, test_malformed_EDGE). In that case, I think it makes sense not to provide any defaults for the constructors of Node and Edge at all, and an immutable default (or, again, no default at all) for the constructor of Graph.