If the messaging app uses a username, then the overwhelming likelihood is that it keeps a serverside database of which usernames are communicating with which other usernames. That problem is the reason apps like Signal use phone numbers instead of usernames --- not because phone numbers are somehow super anonymous, but because it lets them not keep an exposed plaintext contact database on the server.