Described is a system for discovering user interests through online social media, and more specifically, to a way of doing so by means of a bi-directional graph model. During operation, the system generates a confidence matrix F based on user interactions and co-occurring tags on a social media platform. The confidence matrix F indicates a likelihood of the users in the social media platform as being interested in a particular topic. Based on such likelihoods, an action can be initiated regarding a particular topic for those users whose likelihood of being interested in the particular topic exceeds a predetermined threshold. For example, the system generates and presents an online advertisement to users regarding a particular topic to those users whose likelihood of being interested in the particular topic exceeds a predetermined threshold.