Disclosed are methods and systems for generating a suggestion inventory that provides improved user engagement while ensuring privacy of relationships on a social network. The methods and systems include accessing an entity graph that specifies connections between a plurality of users on the social network; identifying a first candidate user of the plurality of users that is indirectly connected to a given user of the plurality of users; computing a number of unique paths on the entity graph between the first candidate user and the given user; determining that the number of unique paths exceeds a first threshold and includes a minimum number of friends of the given user that are directly connected to the given user on the entity graph; and adding the first candidate friend to a friend suggestion inventory for the given user in response to the determination.