Tina Eliassi-Rad Rutgers University Computer Science Given a graph, how can we automatically discover roles (or functions) of nodes? Roles compactly represent structural behaviors of nodes and generalize across various graphs. Examples of roles include "clique-members," "periphery-nodes," "bridges," etc. Are there good features that we can extract for nodes that indicate role-membership? How are roles different from communities and from equivalences (from sociology)? What are the graph-mining applications in which these discovered roles can be effectively used? In this talk, we address these questions, provide unsupervised and supervised algorithms for role discovery, and discuss various applications such as node classification, re-identification, sense-making, and information propagation. Papers associated with this talk were published at KDD’11 (http://eliassi.org/papers/henderson-kdd11.pdf), KDD’12 (http://eliassi.org/papers/henderson-kdd2012.pdf), and KDD’13 (http://eliassi.org/papers/gilpin-kdd2013.pdf).