It doesn't seem possible to maintain the property.

Let's say legal tells us we need a way to let a user delete all of their data. All data is directly or indirectly user data, so we need a request to go to all services.

Examine the first polytree example: https://bytesauna.com/trees/polytree.png

The delete request must go to at least n1 and n4, which can pass below in the heirarchy. If we add some deletion service that connects to both, it's no longer a polytree.

I suppose you could redesign your services to maintain the property, but that would be quite the expense.