Probably completion in a real world application is a strongly domain depending task. And starting from the fact that I am not aware of the specific knowledge represented here, I would speculate that OWL should be a good option, considering that its deductive capabilities can help in completion, at least by obtaining new items, not explicitly defined, and preserving the consistence, by regularly checking.

Can be argued that complexity will be a concern when rising the graph order/size, but you always can easily move from and OWL to other representation, keeping those nodes/edges obtained by deduction. On the other hand, you could consider apply "light weight ontology languages", but it's always depending on domain.

I suggest to be a bit more descriptive, and, BTW, include other keywords, like graph completion, in order to attract the attention the related to the problem specialists.