Facebook has shadow profiles and collects phone numvers feom these contacts.
You could certainly include phone numbers, residential addresses as edges that should be deleted for compliance.
Yes, but that is already legally required. If you aren't storing a name but storing a phone number, and somebody has asked you to delete his personal data, you have broken the law.
That is the easy case, right?
The Ontology problem is one layer harder. The edges I'm describing are inferred i.e, risk scores, behavioral patterns, connections between a person and a geography. There's no standardized form for them and no agreed technical definition of what deletion even means. That's where the enforcement gap is sharpest and what my intention is in writing that piece.