This isn't that difficult to deal with, though. Instead of linking a CEO to their company with a simple object property, explicitly reify the relationship as a class in the model that represents something like "employment". Then you can hang as many contextually relevant properties from the class instance as you need -- start date, end date, role, etc...

This is why much of the hubbub over property graphs puzzles me. If you need a relationship to have its own properties in an RDF graph, just turn it into a class. What's the big deal?