We propose a method to predict users’ interests in social media, using time-evolving, multinomial relational data. We exploit various actions performed by users, and their preferences to predict user interests. Actions performed by users in social media such as Twitter, Delicious and Facebook have two fundamental properties. (a) User actions can be represented as high-dimensional or multinomial relations - e.g. referring URLs, bookmarking and tagging, clicking a favorite button on a post etc. (b) User actions are time-varying and user-specific – each user has unique preferences that change over time. Consequently, it is appropriate to represent each user’s action at some point in time as a multinomial relational data. We propose ActionGraph, a novel graph representation for modeling users’ multinomial, time-varying actions. Each user’s action at some time point is represented by an action node. ActionGraph is a bipartite graph whose edges connect an action node to its involving entities, referred to as object nodes. Using real-world social media data, we empirically justify the proposed graph structure. Our experimental results show that the proposed ActionGraph improves the accuracy in a user interest prediction task by outperforming several baselines including standard tensor analysis, a previously proposed state-of-the-art LDA-based method and other graph-based variants. Moreover, the proposed method shows robust performances in the presence of sparse data.