In social network analysis, the fundamental idea behind the notion of roles is to discover actors who have similar structural signatures. Actors performing the same role have similar behavioural and functional characteristics. Few examples of structural roles are bridge nodes, clique members and star centers. Role discovery involves partitioning the nodes in a network based on their structural characteristics. The notion of roles is complementary to the notion of community detection, which involves partitioning the network into cohesive subgroups. In this paper we propose a novel algorithm RID"Rs (Role Identification and Discovery using “-equitable Refinements): a graph partitioning approach for extracting soft roles in networks. RID"Rs discovers structural roles based on the global graph characteristics of a network. Evaluating the quality of roles discovered is nontrivial due to the lack of ground-truth role datasets, we present a novel framework for evaluating and comparing various role discovery approaches. We also demonstrate the e ectiveness of RID"Rs on diverse graph mining tasks: role identification/discovery and for finding top-k nodes that are most similar to a given node. Further, the empirical scalability analysis of our proposed algorithm on random power-law graphs shows that our approach is highly scalable.