Google Research

Rolx: structural role extraction & mining in large graphs

  • Keith Henderson
  • Brian Gallagher
  • Tina Eliassi-Rad
  • Hanghang Tong
  • Sugato Basu
  • Leman Akoglu
  • Danai Koutra
  • Christos Faloutsos
  • Lei Li
KDD (2012)


Given a network, intuitively two nodes belong to the same role if they have similar structural behavior. Roles should be automatically determined from the data, and could be, for example, “clique-members,” “periphery-nodes,” etc. Roles enable numerous novel and useful network-mining tasks, such as sense-making, searching for similar nodes, and node classification. This paper addresses the question: Given a graph, how can we automatically discover roles for nodes? We propose RolX (Role eXtraction), a scalable (linear in the number of edges), unsupervised learning approach for automatically extracting structural roles from general network data. We demonstrate the e↵ectiveness of RolX on several network-mining tasks: from exploratory data analysis to network transfer learning. Moreover, we compare network role discovery with network community discovery. We highlight fundamental di↵erences between the two (e.g., roles generalize across disconnected networks, communities do not); and show that the two approaches are complimentary in nature.

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work