Then Signal have to store your social graph on the server in plaintext. It's not what's expected from a private messenger.

Storing the social graph is not required at all. For example, Threema creates a random alphanumeric identity that is linked to your public key (instead of linking the phone number directly to your public key). It's possible to optionally link your hashed phone number and/or e-mail to your identity. Finding your friends can be done by comparing hashes of the data in your address book with the hashes linked to the identities. Those address book hashes never need to be persisted anywhere on the server, an in-memory comparison is sufficient, then the data can be thrown away. If you wish to stay anonymous, just ask people to add you manually by typing in your identity (or by scanning your public key QR code, which also results in verification / trust).

Could you elaborate? I don't follow your reasoning here.