As you already concluded in your comment, the only aggregate root should be Graph.
There is a difference between aggregates and aggregate roots. In your example both Graph and Node are aggregates, but the object responsible for managing the entire aggregate is Graph. So this is the root.
The easiest way to get an idea if an object is an aggregate root is to ask yourself:
Does it make sense to have just this object, detached from its parent?
If the answers is no, then it's probably not an aggregate root. For example, a single Node is probably of little use when it's not part of a parent Graph. That's why you usually only have repositories for aggregate roots; to prevent yourself from having access to objects that are not part of their corresponding aggregate root.
Now on to the invariants. You stated that (emphasis mine):
all [Node] names are unique within their parent [Graph]
You basically answered your question right there. In the context of a single Node it doesn't make sense to say that its name is unique. But in the context of a Graph it does, because it is an invariant of the Graph, not the Node. So the Graph is responsible for protecting this invariant.
As for the 'god aggregate root', it's not uncommon to have a single aggregate root from a global business perspective. But an important aspect of DDD is identifying the different contexts within the system. Your system may have a high-level root containing many Graph objects. In this high-level context of managing your graphs, you're probably not even interested in the low-level Link objects in the graph.
It is important that you model your domain objects according to the context. This was one of the most important things I've come to realize in the last few months. Most people know about DDD because of repositories, or maybe because of entities and value objects, but these aren't nearly as important as bounded contexts.
Even though there is only one business concept of Something, it is perfectly fine to have multiple models that represent this concept of Something, a single implementation per context. One implementation might be an aggregate root, while the other implementation is just part of a larger aggregate, all depending on the context.
Common software mantras are about code reuse, DRY and the likes, so at first it felt wrong to have multiple classes that represent the same business concept. But once I was able to let go of this feeling and realize that each implementation had its own responsibilities, it made things so much easier :)