For a counter example, consider Threema. Granted, it can be a rigamarole if you opt out of publishing contact info. But you can. And then backing up and restoring your graph is up to you, or you can rebootstrap people one by one.

On iPhone, after a hardware upgrade w/ restore, Threema offers to restore your client side graph from a client side backup.